92. Reverse Linked List II

 一刷 07/2022

Version #1 Iteration

Time O(N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List II.

Memory Usage: 42.2 MB, less than 24.21% of Java online submissions for Reverse Linked List II.

class Solution {

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left >= right) {

            return head;

        }

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode prev = dummy;

        ListNode curr = head;

        while (curr != null && left > 1) {

            prev = curr;

            curr = curr.next;

            left--;

            right--;

        }

        prev.next = reverseUntil(curr, right);

        return dummy.next;

    }

    

    private ListNode reverseUntil(ListNode head, int right) {

        ListNode prev = null;

        ListNode curr = head;

        ListNode next = null;

        // prev -> curr -> next

        while (curr != null && right > 0) {

            next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

            right--;

        }

        head.next = curr;

        return prev;

    }

}