Linked List Reversal Example: Reversing One Stretch With a Dummy Node

Reversing positions a to b needs the node before a, and a dummy node in front of the head gives position 1 such a node too.

Reversing one stretch of a list, positions a to b counted from 1, uses the same four lines on b − a + 1 nodes and then reconnects the stretch to the nodes on either side. A dummy node is an extra node placed in front of the head that holds no real value, so that every real node, the head included, has a node before it. On 10 20 30 40 50, reversing positions 2 to 4 should give 10 40 30 20 50.

The walk has three parts. Move before from the dummy to the node just before position a. Reverse the stretch with prev starting at null. Then reconnect: the stretch's old first node, still before.next, is now its last, so its next becomes curr, the node after the stretch; and before.next becomes prev, the stretch's new first node.

Reversing positions 2 to 4 of 10 20 30 40 50

Walk to the node before position 2

text

dummy: dummy → 10 → 20 → 30 → 40 → 50 → null
before: 10
curr: 20 → 30 → 40 → 50 → null

Reverse 20

text

before: 10
prev: 20 → null
curr: 30 → 40 → 50 → null

Reverse 30

text

before: 10
prev: 30 → 20 → null
curr: 40 → 50 → null

Reverse 40

text

before: 10
prev: 40 → 30 → 20 → null
curr: 50 → null

Reconnect the stretch

text

after: before.next.next = curr, then before.next = prev
dummy: dummy → 10 → 40 → 30 → 20 → 50 → null
returned: 10 → 40 → 30 → 20 → 50 → null

While the stretch is reversed, 10 still points at 20, which has become the stretch's last node; the two reconnecting lines put 40 after 10 and 50 after 20. The listing runs the same function on positions 2 to 4 and on positions 1 to 2.

stretch.pypy

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


def build(values):
    head = None
    for val in reversed(values):
        node = ListNode(val)
        node.next = head
        head = node
    return head


def values_of(head):
    values = []
    while head:
        values.append(head.val)
        head = head.next
    return values


def reverse_between(head, left, right):
    dummy = ListNode("dummy")
    dummy.next = head
    before = dummy
    for _ in range(left - 1):
        before = before.next
    prev, curr = None, before.next
    for _ in range(right - left + 1):
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    before.next.next = curr
    before.next = prev
    return dummy.next


print("positions 2 to 4:", *values_of(reverse_between(build([10, 20, 30, 40, 50]), 2, 4)))
print("positions 1 to 2:", *values_of(reverse_between(build([10, 20, 30, 40, 50]), 1, 2)))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

positions 2 to 4: 10 40 30 20 50
positions 1 to 2: 20 10 30 40 50

Positions 1 to 2 are the case the dummy exists for. Without it the head has no node before it, so a = 1 would need its own branch that changes which node the function returns. With it, before stays on the dummy, the same two lines reconnect, and dummy.next is the new head whichever stretch was reversed. The walk is O(b) time and O(1) extra space.

Linked Lists

← → move through sections and cards