92 - Reverse Linked List II

Problem

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes from position left to position right (1-indexed) and return the list.

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

• The number of nodes is n, with 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Follow-up: do it in one pass.

Approach

Name the four nodes involved before touching anything. For [1,2,3,4,5], left = 2, right = 4:

1  ->  2  ->  3  ->  4  ->  5
|      |             |      |
bl     l            (r)    after

bl     node before the segment      1
l      first node of the segment    2   -> becomes the segment's TAIL
       last node of the segment     4   -> becomes the segment's HEAD, ends up in prev
after  node after the segment       5

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode dummy(0, head);
        ListNode* bl = &dummy;
        int x = left - 1;
        while(x--) {
            bl = bl->next;
        }
        ListNode* curr = bl->next;
        ListNode* prev = nullptr;
        ListNode* l = curr;
        int n = right - left + 1;
        while(n--) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        bl->next = prev;
        l->next = curr;
        return dummy.next;
    }
};

[1,2,3,4,5], left = 2, right = 4

bl = 1, curr = l = 2, prev = null, n = 3

n=3   next=3   2 -> null          prev=2 curr=3
n=2   next=4   3 -> 2             prev=3 curr=4
n=1   next=5   4 -> 3             prev=4 curr=5

bl->next = prev   1 -> 4
l->next  = curr   2 -> 5

1 -> 4 -> 3 -> 2 -> 5

• time: O(n) - left - 1 steps to the seam, then right - left + 1 to reverse
• space: O(1) - four pointers and a stack-allocated dummy