Module 11 · Linked Lists and Pointer Mutation

108. Reverse a Sublist

Interview · Download this solution · All solutions and shared helpers

Problem

Reverse the nodes at one-based positions left through right, inclusive, in a finite singly linked list. Assume 1<=left<=right<=length. Return the resulting head, preserving all nodes and links outside the specified segment.

Examples

Example 1

list_values(reverse_sublist(build_list([1,2,3,4,5]), 2, 4))
=> [1, 4, 3, 2, 5]

Only the inclusive middle segment is reversed.

Example 2

list_values(reverse_sublist(build_list([1,2,3]), 1, 3))
=> [3, 2, 1]

The dummy also supports reversing from the head.

Example 3

list_values(reverse_sublist(build_list([7]), 1, 1))
=> [7]

A one-node segment requires no transfers.

Reveal the worked solution and reasoning

Why this mechanism works

Keep an anchor immediately before the segment. Repeatedly remove the node after the segment's original first node and insert it immediately after the anchor. Each move extends the reversed prefix while the original first node becomes the fixed tail of the reversed region.

State and boundaries

before is the anchor. current is the original first segment node and remains its tail. moving is the next node transferred to the front.

Protocol

Use a dummy and locate before.
Set current=before.next.
Repeat right-left times: detach current.next.
Insert that detached node immediately after before.
Return dummy.next.

Visualization

1 -> [2 -> 3 -> 4] -> 5
move 3 to front: 1 -> [3 -> 2 -> 4] -> 5
move 4 to front: 1 -> [4 -> 3 -> 2] -> 5

Python implementation

from structures import ListNode, build_list, list_values

def reverse_sublist(head, left, right):
    dummy = ListNode(next=head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    current = before.next
    for _ in range(right - left):
        moving = current.next
        current.next = moving.next
        moving.next = before.next
        before.next = moving
    return dummy.next

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

list_values(reverse_sublist(build_list([1,2,3,4,5]), 2, 4))

L4 reverse_sublist: dummy = ListNode(next=head)
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None)

L5 reverse_sublist: before = dummy
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None)

L6 reverse_sublist: for _ in range(left - 1):
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None); _=0

L7 reverse_sublist: before = before.next
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N2,random=None); _=0

L8 reverse_sublist: current = before.next
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N2,random=None); _=0; current=N2(val=2,next=N4,random=None)

L10 reverse_sublist: moving = current.next
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N2,random=None); _=0; current=N2(val=2,next=N4,random=None); moving=N4(val=3,next=N5,random=None)

L11 reverse_sublist: current.next = moving.next
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N2,random=None); _=0; current=N2(val=2,next=N5,random=None); moving=N4(val=3,next=N5,random=None)

L12 reverse_sublist: moving.next = before.next
head=N1(val=1,next=N2,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N2,random=None); _=0; current=N2(val=2,next=N5,random=None); moving=N4(val=3,next=N2,random=None)

... 2 intermediate state changes omitted ...

L10 reverse_sublist: moving = current.next
head=N1(val=1,next=N4,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N4,random=None); _=1; current=N2(val=2,next=N5,random=None); moving=N5(val=4,next=N6,random=None)

L11 reverse_sublist: current.next = moving.next
head=N1(val=1,next=N4,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N4,random=None); _=1; current=N2(val=2,next=N6,random=None); moving=N5(val=4,next=N6,random=None)

L12 reverse_sublist: moving.next = before.next
head=N1(val=1,next=N4,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N4,random=None); _=1; current=N2(val=2,next=N6,random=None); moving=N5(val=4,next=N4,random=None)

L13 reverse_sublist: before.next = moving
head=N1(val=1,next=N5,random=None); left=2; right=4; dummy=N3(val=0,next=N1,random=None); before=N1(val=1,next=N5,random=None); _=1; current=N2(val=2,next=N6,random=None); moving=N5(val=4,next=N4,random=None)

Result: [1, 4, 3, 2, 5]. Only the inclusive middle segment is reversed.

list_values(reverse_sublist(build_list([1,2,3]), 1, 3))

L4 reverse_sublist: dummy = ListNode(next=head)
head=N1(val=1,next=N2,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None)

L5 reverse_sublist: before = dummy
head=N1(val=1,next=N2,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None)

L8 reverse_sublist: current = before.next
head=N1(val=1,next=N2,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None); current=N1(val=1,next=N2,random=None)

L9 reverse_sublist: for _ in range(right - left):
head=N1(val=1,next=N2,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None); current=N1(val=1,next=N2,random=None); _=0

L10 reverse_sublist: moving = current.next
head=N1(val=1,next=N2,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None); current=N1(val=1,next=N2,random=None); _=0; moving=N2(val=2,next=N4,random=None)

L11 reverse_sublist: current.next = moving.next
head=N1(val=1,next=N4,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None); current=N1(val=1,next=N4,random=None); _=0; moving=N2(val=2,next=N4,random=None)

L12 reverse_sublist: moving.next = before.next
head=N1(val=1,next=N4,random=None); left=1; right=3; dummy=N3(val=0,next=N1,random=None); before=N3(val=0,next=N1,random=None); current=N1(val=1,next=N4,random=None); _=0; moving=N2(val=2,next=N1,random=None)

L13 reverse_sublist: before.next = moving
head=N1(val=1,next=N4,random=None); left=1; right=3; dummy=N3(val=0,next=N2,random=None); before=N3(val=0,next=N2,random=None); current=N1(val=1,next=N4,random=None); _=0; moving=N2(val=2,next=N1,random=None)

... 1 intermediate state changes omitted ...

L10 reverse_sublist: moving = current.next
head=N1(val=1,next=N4,random=None); left=1; right=3; dummy=N3(val=0,next=N2,random=None); before=N3(val=0,next=N2,random=None); current=N1(val=1,next=N4,random=None); _=1; moving=N4(val=3,next=None,random=None)

L11 reverse_sublist: current.next = moving.next
head=N1(val=1,next=None,random=None); left=1; right=3; dummy=N3(val=0,next=N2,random=None); before=N3(val=0,next=N2,random=None); current=N1(val=1,next=None,random=None); _=1; moving=N4(val=3,next=None,random=None)

L12 reverse_sublist: moving.next = before.next
head=N1(val=1,next=None,random=None); left=1; right=3; dummy=N3(val=0,next=N2,random=None); before=N3(val=0,next=N2,random=None); current=N1(val=1,next=None,random=None); _=1; moving=N4(val=3,next=N2,random=None)

L13 reverse_sublist: before.next = moving
head=N1(val=1,next=None,random=None); left=1; right=3; dummy=N3(val=0,next=N4,random=None); before=N3(val=0,next=N4,random=None); current=N1(val=1,next=None,random=None); _=1; moving=N4(val=3,next=N2,random=None)

Result: [3, 2, 1]. The dummy also supports reversing from the head.

Why the solution is correct

After t transfers, the first t+1 original segment nodes are reversed after the anchor, and current links to the unread segment suffix. One transfer preserves that form. After right-left transfers the entire requested segment is reversed and its outside connections are intact.

Time and space

O(length) time in the worst case and O(1) auxiliary space.

Common mistakes

Moving the anchor during reversal loses the insertion point. Detaching without first retaining moving loses the node being repositioned.

Reasoning card

State: before is the anchor. current is the original first segment node and remains its tail. moving is the next node transferred to the front.

Invariant: Nodes before predecessor and after the active sublist remain connected correctly.

Decision to rehearse: Detach via a dummy predecessor and repeatedly move nodes to the front of the sublist.

Finish: Return dummy.next

Transfer exercise

Reverse nodes in groups of k, deciding explicitly what happens to a final incomplete group.