92. Reverse Linked List II

,

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode pre = dummyHead;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        ListNode subHead = pre.next;
        ListNode subTail = subHead;
        for (int i = 0; i < right - left; i++) {
            subTail = subTail.next;
        }

        ListNode next = subTail.next;

        pre.next = null;
        subTail.next = null;

        reverse(subHead);

        pre.next = subTail;
        subHead.next = next;

        return dummyHead.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null, curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode subHeadPre = dummyHead;
        for (int i = 0; i < left - 1; i++) {
            subHeadPre = subHeadPre.next;
        }

        ListNode subHead = subHeadPre.next;
        ListNode curr = subHead;
        ListNode pre = null;
        for (int i = 0; i <= right - left; i++) { // 注意此处的索引，首次处理时 curr.next 会指向空，curr 最后将停留在子链表的后一个节点上
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        subHeadPre.next = pre;
        subHead.next = curr;

        return dummyHead.next;
    }
}

Iterate + Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private static class SuccHolder {
        private ListNode succ;
    }

    public ListNode reverseTheFirstNNodes(ListNode head, int n, SuccHolder succHolder) {
        if (n == 1) {
            succHolder.succ = head.next;
            return head;
        }

        ListNode newHead = reverseTheFirstNNodes(head.next, n - 1, succHolder);
        head.next.next = head;
        head.next = succHolder.succ; // 虽然中间节点的 next 指向了 succ, 但是会在后续递归回退的过程中被 head.next.next 修正 next 指向
        return newHead;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode prev = dummyHead;
        for (int i = left - 1; i > 0; i--) {
            prev = prev.next;
        }

        prev.next = reverseTheFirstNNodes(prev.next, right - left + 1, new SuccHolder());
        return dummyHead.next;
    }
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private static class SuccHolder {
        private ListNode succ;
    }

    public ListNode reverseTheFirstNNodes(ListNode head, int n, SuccHolder succHolder) {
        if (n == 1) {
            succHolder.succ = head.next;
            return head;
        }

        ListNode newHead = reverseTheFirstNNodes(head.next, n - 1, succHolder);
        head.next.next = head;
        head.next = succHolder.succ; // 虽然中间节点的 next 指向了 succ, 但是会在后续递归回退的过程中被 head.next.next 修正 next 指向
        return newHead;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseTheFirstNNodes(head, right - left + 1, new SuccHolder());
        }

        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
}

References

92. Reverse Linked List II