Leetcode 206：Reverse Linked List

Reverse a singly linked list.

[法1] 穿针引线

思路

定义三个指针：

• pre：前一个指针
• cur：当前指针
• next：下一个指针

慢慢穿针引线，先用 next 记下后面的链表，防止丢失，然后将 cur 指针从 pre->cur->next 转为 pre<-cur next->，直到遍历完整个链表。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        //前指针
        ListNode pre = null;
        //当前指针
        ListNode cur = head;

        while(cur != null){
            //下一个指针
            ListNode next = cur.next;
            //反转当前指针：从 pre->cur->next 转为 pre<-cur next->
            cur.next = pre;
            //往后
            pre = cur;
            //往后
            cur = next;
        }
        //跳出 while 循环的时候 cur 是NULL，所以头指针是前一个指针pre
        return pre;
    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[法2] 递归

思路

null <- 1 <- 2 <- 3 <-4 5->null 和 null <- 1 <- 2 <- 3 <-4 <- 5 的差别就在于把 5(cur) 指向前面的 4(pre)；

null <- 1 <- 2 <- 3 4 -> 5->null 和 null <- 1 <- 2 <- 3 <-4 5 -> null 的差别就在于把 4(cur) 指向前面的 3(pre)；

null <- 1 <- 2 3 -> 4 -> 5->null 和 null <- 1 <- 2 3 -> 4 -> 5 -> null 的差别就在于把 3(cur) 指向前面的 2(pre)；

所以我们递归的内核就是不断的将 pre 和 cur 进行反转，递归出口是：cur == null

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        //pre = null; cur = head;
        return reverse(null,head);

    }

    /**
     * 反转：将 pre->cur->next 转为 pre<-cur next->
     * @param pre: 前一个节点
     * @param cur: 当前结点
     */
    public ListNode reverse(ListNode pre,ListNode cur){

        //如果当前结点已经空了，说明链表已经结束了，直接返回 pre
        if(cur == null){
            return pre;
        }
        ListNode next = cur.next;
        //反转链表
        cur.next = pre;
        //递归下去
        return reverse(cur,next);
        
    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)