DSA sheet · Linked List · Reversal pattern

Reverse Linked List II

So far the reversal pattern reversed a whole list (or a whole half). Now we reverse only a window: from position left to position right, and the rest of the list must stay where it is. The teacher first shows the copy-into-an-array brute force, then the in-place solution: walk to the node just before the window, reverse exactly right − left + 1 nodes with the usual prev / curr / nxt, then stitch the two ends back in. She also shows, by running a failing test on screen, why we need a dummy node and must return dummy.next instead of head. The "reverse a window and reconnect" move is the core of Reverse Nodes in k-Group later.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists, reversal and the dummy node from scratch
• Part A · Brute force: copy values, swap the window, write back
• Part B · Optimal: in-place window reversal with a dummy node
• Part C · Revision page

Part 0 · What you must know before starting

Nodes, head, None and walking

A linked list is a chain of nodes. Each node has a value val and a link next to the node after it. The last node points to None. We're given the first node, the head. To move along we use a walker: curr = curr.next.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

[1] → [2] → [3] → [4] → [5] → [6] → None
head
position: 1     2     3     4     5     6      (this problem counts from 1)

There's no index access: to reach position i you must follow i − 1 arrows from the head (O(i) time). And you can't step backwards.

Save next before changing a pointer

A node's next is the only road to everything after it. Overwrite it without saving and that part of the list is lost. So we always store nxt = curr.next first.

Reversal with prev / curr / nxt (from "Reverse a Linked List")

nxt = curr.next     # 1. save the road ahead
curr.next = prev    # 2. flip this node's arrow backward
prev = curr         # 3. prev moves up
curr = nxt          # 4. curr moves up

Two facts we'll use: after flipping some nodes, prev is on the last node flipped (the new front of the reversed piece), and curr is on the first node not flipped (just outside the piece).

The dummy node

A dummy is a fake extra node we put in front of the head: dummy = ListNode(0, head). Its value doesn't matter.

[D] → [1] → [2] → [3] → ...
dummy head

Why bother? Many list operations need "the node before" some position. Every real node has one, except the head. Without a dummy you'd need special code for "what if the change starts at the head?". With a dummy, even the head has a node before it, so one piece of code handles every case. And at the end, dummy.next is always the real first node, even if the old head moved somewhere else.

In-place

The teacher's term: a linked-list solution is in-place when it only rewires the existing nodes and uses no extra list or array. That's what "optimal" means here.

Part A · Brute force: copy values, swap the window, write back

LeetCode 92

1The question in simple words

You get head and two positions left ≤ right (counting from 1). Reverse only the nodes from position left to position right and return the head of the resulting list.

input:  [1] → [2] → [3] → [4] → [5] → [6] → None,  left = 2, right = 4
                └─── reverse this ───┘
output: [1] → [4] → [3] → [2] → [5] → [6] → None

That's the teacher's list. LeetCode's examples: [1,2,3,4,5], left=2, right=4 → [1,4,3,2,5] and [5], left=1, right=1 → [5].

2What the constraints tell us

• Number of nodes: 1 to 500 → small. Any linear idea passes easily. As usual in linked lists, she treats 2n, 3n, 4n passes as "brute force" and one clean n (or n/2) pass as "optimal".
• 1 ≤ left ≤ right ≤ n → the window is always inside the list. left can be 1 (window starts at the head, see the dummy node), and right can be n (window reaches the tail). Both together means "reverse everything".
• left == right is allowed → a window of one node. Reversing one node changes nothing.
• Values −500 to 500 → nothing special.

3Intuition: pretend we can't reverse a list yet

If we copy the values into an array, the window is just a range of indices. Position left is index left − 1, position right is index right − 1. Reversing a range of an array is the classic two-pointer swap. Then we write the array back into the nodes.

4Building the logic

vals = [1, 2, 3, 4, 5, 6]        left = 2 → i = 1,  right = 4 → j = 3
        i=1, j=3 → swap → [1, 4, 3, 2, 5, 6]
        i=2, j=2 → they meet → stop (the 3 stays)

• Swap with a temporary variable (her Java code uses temp; Python can also do a, b = b, a).
• Stop while i < j: odd-sized windows end with i == j (the middle stays), even-sized ones end with i > j.
• Then walk the list from head again and overwrite every node's value with vals[k], k = 0, 1, 2, … The nodes outside the window simply get their own value back.
• The links never change, so the first node is still the first node → return head.

5Approach steps

1. Copy every value into vals.
2. i = left - 1, j = right - 1. While i < j: swap vals[i], vals[j]; i += 1; j -= 1.
3. Walk the list again from head, writing vals[0], vals[1], … into the nodes.
4. Return head.

6Code (Python)

class Solution:
    def reverseBetween(self, head, left, right):
        vals = []
        curr = head
        while curr:                      # 1. copy values out
            vals.append(curr.val)
            curr = curr.next

        i, j = left - 1, right - 1       # 2. positions → indexes
        while i < j:                     #    reverse the window in the array
            temp = vals[i]
            vals[i] = vals[j]
            vals[j] = temp
            i += 1
            j -= 1

        curr = head                      # 3. write everything back
        k = 0
        while curr:
            curr.val = vals[k]
            k += 1
            curr = curr.next
        return head

7Code line by line

8Dry run

9Complexity & remember

• Time: n (copy) + (right − left + 1)/2 (swaps) + n (write back). In the worst case the window is the whole list (left = 1, right = n), so it's n + n/2 + n = 5n/2. Linear, but three passes.
• Space O(n) for the array.

Part B · Optimal: in-place window reversal with a dummy node

1The question (same), new goal

Same output, but in-place (no array) and in one pass. LeetCode's follow-up asks exactly that.

2What the constraints tell us

• left can be 1 → the window can start at the head, which has no node before it → dummy node.
• left == right → nothing to reverse → return head straight away.
• n ≥ 1, so head is never None. We still keep head is None in the base case, the way the teacher says to always think about it.

3Intuition: reverse the window, then fix its two ends

Stand on the first node of the window, [2], and run the normal reversal over the window only. When it's done:

• prev is on [4], the last window node, which is now the front of the reversed piece.
• curr is on [5], the first node after the window.
• [2], the old front of the window, is now its back.

The reversed piece is correct inside, but its two ends are loose. Two links fix it:

1. the node before the window ([1]) must point to the new front [4] = prev;
2. the old front [2] must point to the node after the window [5] = curr.

So before reversing we need a pointer to the node before the window. The teacher calls it previous-left (prev_left), and the old front [2] she calls the left node ("leftover node", left_node).

4Building the logic step by step

Step 1: put a dummy in front and walk left − 1 jumps

prev_left starts at the dummy and jumps left − 1 times. With left = 2 that's 1 jump, landing on [1], the node just before position 2. Then curr = prev_left.next is the first window node and prev = None.

start: prev_left = dummy
[D] → [1] → [2] → [3] → [4] → [5] → [6] → None
dummy/prev_left

left − 1 = 1 jump: prev_left = prev_left.next
[D] → [1] → [2] → [3] → [4] → [5] → [6] → None
dummy  ↑
    prev_left

curr = prev_left.next, prev = None
[D] → [1] → [2] → [3] → [4] → [5] → [6] → None
dummy  ↑    curr
    prev_left

Step 2: reverse exactly right − left + 1 nodes

The window holds right − left + 1 nodes (positions 2, 3, 4 → 3 nodes). We run the four reversal lines that many times. The red arrow is the one just flipped. Only the window piece is drawn on the main line; the part before it is unchanged.

[D] → [1] → [2]   ([1] still points to [2] the whole time)

① nxt = curr.next  (→ [3])
None   [2] → [3] → [4] → [5] → [6] → None
prev   curr  nxt

② curr.next = prev  ([2].next: [3] → None)
None ← [2]   [3] → [4] → [5] → [6] → None
prev   curr  nxt

③ prev = curr, curr = nxt
None ← [2]   [3] → [4] → [5] → [6] → None
       prev  curr

[D] → [1] → [2]   ([1] still points to [2] the whole time)

① nxt = curr.next  (→ [4])
None ← [2]   [3] → [4] → [5] → [6] → None
       prev  curr  nxt

② curr.next = prev  ([3].next: [4] → [2])
None ← [2] ← [3]   [4] → [5] → [6] → None
       prev  curr  nxt

③ prev = curr, curr = nxt
None ← [2] ← [3]   [4] → [5] → [6] → None
             prev  curr

[D] → [1] → [2]   ([1] still points to [2] the whole time)

① nxt = curr.next  (→ [5])
None ← [2] ← [3]   [4] → [5] → [6] → None
             prev  curr  nxt

② curr.next = prev  ([4].next: [5] → [3])
None ← [2] ← [3] ← [4]   [5] → [6] → None
             prev  curr  nxt

③ prev = curr, curr = nxt
None ← [2] ← [3] ← [4]   [5] → [6] → None
                   prev  curr

Step 3: stitch both ends

State after the loop (one picture, all pointers):

[D] → [1] → [2] ← [3] ← [4]   [5] → [6] → None
             ↓
            None
prev_left = [1]   ([1].next is still [2])   prev = [4]   curr = [5]

First grab the old front: left_node = prev_left.next → [2]. Nobody touched [1]'s arrow, so it still leads to [2].

Now the two links:

a) prev_left.next = prev        ([1].next: [2] → [4])
[D] → [1] → [4] → [3] → [2] → None          and   [5] → [6] → None (loose for now)

b) left_node.next = curr        ([2].next: None → [5])
[D] → [1] → [4] → [3] → [2] → [5] → [6] → None   ✓

Step 4: return dummy.next, not head

For the example above, head is still [1] and still first, so returning head would happen to work. The teacher shows why that's luck by changing the test on screen to [1,2,3,4,5], left = 1, right = 4:

before:  [D] → [1] → [2] → [3] → [4] → [5] → None      prev_left = dummy (0 jumps)
after:   [D] → [4] → [3] → [2] → [1] → [5] → None
               dummy.next              head is still here

• return head → the list read from [1] is [1] → [5] → wrong answer "1, 5" (this is what she got on screen).
• return dummy.next → 4 → 3 → 2 → 1 → 5 → correct. The dummy always points at whatever is first now.

Base case

If left == right, the window is a single node; reversing it means nothing ("from node 2 to node 2" is no reversal). Also if there's no head there's nothing to do. Return head immediately.

5Approach steps

1. If head is None or left == right → return head.
2. dummy = ListNode(0, head); prev_left = dummy; jump left − 1 times.
3. prev = None, curr = prev_left.next.
4. Repeat right − left + 1 times: nxt = curr.next; curr.next = prev; prev = curr; curr = nxt.
5. left_node = prev_left.next (old front of the window).
6. prev_left.next = prev (before-window → new front).
7. left_node.next = curr (new back → after-window).
8. Return dummy.next.

6Code (Python)

class Solution:
    def reverseBetween(self, head, left, right):
        if head is None or left == right:      # nothing to reverse
            return head

        dummy = ListNode(0, head)              # a node before the head
        prev_left = dummy
        for _ in range(left - 1):              # land on the node before the window
            prev_left = prev_left.next

        prev = None
        curr = prev_left.next                  # first node of the window
        for _ in range(right - left + 1):      # flip exactly the window
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        # now: prev = new front of the window, curr = first node after it

        left_node = prev_left.next             # old front, will be the back
        prev_left.next = prev                  # before-window → new front
        left_node.next = curr                  # new back → after-window
        return dummy.next                      # correct even when left == 1

7Code line by line

8Dry runs

Teacher's example: [1..6], left = 2, right = 4

1. left ≠ right → go on. dummy → [1]. prev_left jumps once → [1].
2. curr = [2], prev = None. 3 rounds (drawn above): [2]→None, [3]→[2], [4]→[3]. Now prev = [4], curr = [5].
3. left_node = [1].next = [2].
4. [1].next = [4] → reading from the dummy: D, 1, 4, 3, 2, then None.
5. [2].next = [5] → D, 1, 4, 3, 2, 5, 6.
6. Return dummy.next = [1] → 1 → 4 → 3 → 2 → 5 → 6 ✓

Window at the head: [1..5], left = 1, right = 4

Return dummy.next = [4] ✓. (head = [1] would give 1 → 5.)

Window at the tail: [1, 2, 3], left = 2, right = 3

prev_left = [1]; 2 rounds flip [2], [3]; prev = [3], curr = None. [1].next = [3], [2].next = None → 1 → 3 → 2 ✓. So left_node.next = curr also correctly ends the list when the window reaches the tail.

9Complexity & remember

• Time O(n): left − 1 jumps to reach the window, then right − left + 1 flips. Together that's at most right ≤ n steps, one pass, and we never look at nodes after the window.
• Space O(1): a dummy node and a handful of pointers.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.reverseBetween(build([1, 2, 3, 4, 5, 6]), 2, 4)))   # [1, 4, 3, 2, 5, 6]
print(to_list(s.reverseBetween(build([1, 2, 3, 4, 5]), 1, 4)))      # [4, 3, 2, 1, 5]
print(to_list(s.reverseBetween(build([5]), 1, 1)))                  # [5]
print(to_list(s.reverseBetween(build([1, 2, 3]), 2, 3)))            # [1, 3, 2]

Based on this video: Reverse Linked List II | Reversal pattern