Reverse Linked List II

How it works

This approach reverses in a single pass without explicitly detaching the sublist. After finding the node before the reversal starts, we reverse links one at a time as we traverse. The key is maintaining a reference to the original sublist head (which becomes the tail after reversal) so we can reconnect it to the node following the reversed section.

Steps

1. Create a dummy node pointing to the head.
2. Traverse left - 1 steps to position leftPrev (node before reversal) and cur (first node to reverse).
3. Reverse right - left + 1 nodes in place:
   • Save cur.next as tmpNext.
   • Point cur.next to prev.
   • Advance prev to cur and cur to tmpNext.
4. After the loop, prev points to the new head of the reversed section and cur points to the node after it.
5. Connect leftPrev.next.next (original first node, now last) to cur.
6. Connect leftPrev.next to prev (the new head).
7. Return dummy.next.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Not Using a Dummy Node for Edge Cases

When left equals 1, the head of the list changes after reversal. Without a dummy node pointing to the head, you lose the reference to the new head and cannot return the correct result. The dummy node provides a stable anchor that simplifies edge case handling when the reversal starts at the beginning.

Forgetting to Reconnect the Reversed Sublist

After reversing the sublist, both ends must be reconnected to the rest of the list. A common mistake is connecting only one end, either forgetting to link the node before position left to the new sublist head, or forgetting to link the new sublist tail to the node after position right. Both connections are essential.

Incorrect Pointer Updates During In-Place Reversal

The single-pass reversal approach requires careful tracking of multiple pointers. A frequent error is updating leftPrev.next before using it to access the original sublist head. Since leftPrev.next initially points to the first node being reversed (which becomes the tail), you must save this reference or use it correctly before overwriting it with the new head.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        leftPrev, cur = dummy, head

        for _ in range(left - 1):
            leftPrev, cur = cur, cur.next

        prev = None
        for _ in range(right - left + 1):
            tmpNext = cur.next
            cur.next = prev
            prev, cur = cur, tmpNext

        leftPrev.next.next = cur
        leftPrev.next = prev

        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* leftPrev = &dummy;
        ListNode* cur = head;

        for (int i = 0; i < left - 1; ++i) {
            leftPrev = cur;
            cur = cur->next;
        }

        ListNode* prev = nullptr;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode* tmpNext = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmpNext;
        }

        leftPrev->next->next = cur;
        leftPrev->next = prev;

        return dummy.next;
    }
};