92. Reverse Linked List II

Iterate

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        ListNode dummyHead = new ListNode(-1, head);
        // d 1 2 3 4 5, when left = 2, right = 4
        // d   l   r
        ListNode curr = dummyHead;
        for (int i = 0; i < left - 1; i++) {
            curr = curr.next;
        }
        // d 1 2 3 4 5
        //   c
        ListNode leftTail = curr;
        for (int i = 0; i < right - left + 1; i++) {
            curr = curr.next;
        }
        // d 1 2 3 4 5
        //         c
        ListNode midTail = curr;
        ListNode midHead = leftTail.next;
        leftTail.next = null;
        ListNode rightHead = midTail.next;
        midTail.next = null;
        ListNode reversedMidHead = reverse(midHead);
        leftTail.next = reversedMidHead;
        midHead.next = rightHead;
        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

class Solution {
    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;
        }

        ListNode newSubTail = prev.next;
        ListNode curr = prev.next;
        ListNode pre = null;
        while (right >= left) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
            right--;
        }

        prev.next = pre;
        newSubTail.next = curr;

        return dummyHead.next;
    }
}

Iterate + Recursion

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

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;
    }
}

Reference

92. Reverse Linked List II