206. Reverse Linked List

,

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;
    }
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);
    }

    private ListNode recur(ListNode node, ListNode pre) {
        if (node == null) {
            return pre; // 注意此处返回 pre
        }

        ListNode newHead = recur(node.next, node);
        node.next = pre; // 注意此处修改的事 node.next 而不是 newHead.next, 因为需要修改所有节点的 next 而不仅仅是最后一个节点的 next
        return newHead;
    }
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);
    }

    private ListNode recur(ListNode node, ListNode pre) {
        if (node == null) {
            return pre;
        }

        ListNode next = node.next;
        node.next = pre;
        return recur(next, node);
    }
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

References

206. Reverse Linked List
剑指 Offer 24. 反转链表
剑指 Offer II 024. 反转链表