Pointer Manipulation

Linked List Pointer Manipulation

Linked list problems that ask you to reverse, reorder, or rewire nodes all share a common requirement: you must update next pointers in exactly the right order, or you lose your reference to the rest of the list. This article walks through the core patterns you need, starting from the simplest, list reversal, and building up to more complex operations like reversing in groups and reordering the entire list.

The prev/curr/next Reversal Pattern

LeetCode 206 is the fundamental operation from which almost everything else is built: reversing a singly linked list. You maintain three pointers (prev, curr, and nxt) and advance them together through the list, flipping each next pointer as you go.

The order of operations inside the loop matters critically. You must save curr.next into nxt before you overwrite curr.next = prev, because once you change that pointer, you have no way to reach the rest of the list.

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next      # save before overwriting
        curr.next = prev     # flip the pointer
        prev = curr          # advance prev
        curr = nxt           # advance curr
    return prev              # prev is the new head

Walked Example: Reversing 1 -> 2 -> 3 -> 4

Start: prev = None, curr = 1.

Step 1. nxt = 2. curr.next = None (1 now points nowhere). prev = 1, curr = 2. State: None <- 1 2 -> 3 -> 4

Step 2. nxt = 3. curr.next = 1 (2 now points back to 1). prev = 2, curr = 3. State: None <- 1 <- 2 3 -> 4

Step 3. nxt = 4. curr.next = 2. prev = 3, curr = 4. State: None <- 1 <- 2 <- 3 4

Step 4. nxt = None. curr.next = 3. prev = 4, curr = None. State: None <- 1 <- 2 <- 3 <- 4

The loop exits because curr is None. Return prev, which is 4, the new head of the reversed list.

Dummy Nodes for Simpler Head Operations

Many list problems require inserting nodes before the current head or splitting a list into two. Without a dummy node, you must write special-case logic for the first insertion. A dummy node eliminates that by giving you a node that sits before the real head, so every insertion is a "middle" insertion.

dummy = ListNode(0)
dummy.next = head
curr = dummy

# ... manipulate curr.next freely ...

return dummy.next  # the actual result head

This trick appears in partition list, reverse in groups of k, and nearly any problem that might return a different head than the input.

Reorder List: Find Middle, Reverse Second Half, Merge

LeetCode 143. Reorder List asks you to reorder a list from L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> .... This problem composes three techniques in sequence.

Step 1: Find the middle. Use the slow/fast pointer technique. When fast reaches the end, slow is at the midpoint.

Step 2: Reverse the second half. Call the reversal function on slow.next, then sever the connection at slow so the first half terminates properly.

Step 3: Merge the two halves alternately. Interleave nodes from the front and back, advancing two pointers simultaneously.

def reorder_list(head):
    if not head or not head.next:
        return

    # Step 1: find the middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: reverse the second half
    second = reverse_list(slow.next)
    slow.next = None   # sever the first half

    # Step 3: merge alternately
    first = head
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

def reverse_list(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

Notice that in the merge phase, second is always shorter than or equal to first (the second half is at most as long as the first). The loop terminates when second runs out, leaving any remaining first nodes in place, which is exactly what we want.

Reverse in Groups of K

LeetCode 25. Reverse Nodes in k-Group extends reversal to groups: given k, reverse every k consecutive nodes. If fewer than k nodes remain at the tail, leave them as-is.

The key challenge is connecting reversed groups together. After reversing a group, the original first node of that group becomes its tail and needs to connect to the head of the next reversed group. A dummy node before the whole list makes this uniform.

def reverse_k_group(head, k):
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy

    while True:
        # Check if k nodes remain
        kth = get_kth(group_prev, k)
        if not kth:
            break

        group_next = kth.next

        # Reverse the group
        prev, curr = kth.next, group_prev.next
        while curr != group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # Re-connect: group_prev -> new head (kth), old head (group_prev.next) -> group_next
        tmp = group_prev.next
        group_prev.next = kth
        tmp.next = group_next
        group_prev = tmp

    return dummy.next

def get_kth(curr, k):
    while curr and k > 0:
        curr = curr.next
        k -= 1
    return curr

Partition List

LeetCode 86. Partition List asks you to rearrange a list so all nodes with value less than x come before nodes with value >= x, preserving relative order within each group.

The cleanest approach uses two dummy heads: one for the "less" partition and one for the "greater-or-equal" partition. Iterate through the original list, appending each node to the appropriate partition. At the end, connect the tail of the "less" partition to the head of the "greater" partition, and set the "greater" tail's next to None.

def partition(head, x):
    less_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    less = less_dummy
    greater = greater_dummy

    curr = head
    while curr:
        if curr.val < x:
            less.next = curr
            less = less.next
        else:
            greater.next = curr
            greater = greater.next
        curr = curr.next

    greater.next = None          # avoid a cycle
    less.next = greater_dummy.next
    return less_dummy.next

Setting greater.next = None is easy to forget and causes a cycle when the last node of the greater partition originally pointed to a node that ended up in the less partition.

Remove the Nth Node from End

LeetCode 19. Remove Nth Node From End of List asks you to remove the nth node from the end of a linked list in one pass. The trick is a two-pointer gap: advance a leader pointer n steps ahead of a follower. Then move both forward together. When leader reaches the end, follower is right before the node you need to remove.

A dummy node handles the edge case where the node to remove is the head itself.

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    leader = dummy
    follower = dummy

    # Advance leader n + 1 steps so the gap is n
    for _ in range(n + 1):
        leader = leader.next

    # Move both until leader hits the end
    while leader:
        leader = leader.next
        follower = follower.next

    # follower.next is the node to remove
    follower.next = follower.next.next
    return dummy.next

Swap Nodes in Pairs

LeetCode 24. Swap Nodes in Pairs asks you to swap every two adjacent nodes. The key is maintaining a pointer to the node before each pair so you can rewire both forward links. A dummy node before the head makes the first pair uniform with the rest.

def swap_pairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while prev.next and prev.next.next:
        a = prev.next
        b = prev.next.next

        # rewire
        a.next = b.next
        b.next = a
        prev.next = b

        prev = a  # a is now the tail of the swapped pair

    return dummy.next

For each pair a -> b, we point a.next past b, point b.next back to a, and point prev.next to b. Then advance prev to a, which is now the second node in the pair and sits right before the next pair.

Rotate List

LeetCode 61. Rotate List asks you to rotate a linked list to the right by k places. The insight is that rotation is equivalent to forming a cycle and breaking it at the right spot.

First, walk the list to find its length and tail. Connect the tail to the head to form a ring. Then advance from the tail (length - k % length) steps to find the new tail. Break the cycle there.

def rotate_right(head, k):
    if not head or not head.next or k == 0:
        return head

    # Find length and tail
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1

    # Form a cycle
    tail.next = head

    # Find the new tail: (length - k % length) steps from current tail
    steps = length - k % length
    new_tail = tail
    for _ in range(steps):
        new_tail = new_tail.next

    new_head = new_tail.next
    new_tail.next = None
    return new_head

Copy List with Random Pointer

LeetCode 138. Copy List with Random Pointer asks you to deep copy a linked list where each node has an extra random pointer that can point to any node or null. The interleaving trick solves this in O(1) extra space.

Step 1: Weave copies between originals. For each node A, create A' and insert it right after A, so the list becomes A -> A' -> B -> B' -> ...

Step 2: Set random pointers. For each original node A, A'.random = A.random.next (because A.random's copy is the node right after A.random).

Step 3: Separate the two lists. Restore the original list and extract the copy list.

def copy_random_list(head):
    if not head:
        return None

    # Step 1: interleave copies
    curr = head
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next

    # Step 2: assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Step 3: separate the two lists
    curr = head
    copy_head = head.next
    while curr:
        copy = curr.next
        curr.next = copy.next
        curr = curr.next
        if curr:
            copy.next = curr.next

    return copy_head

Sort List

LeetCode 148. Sort List asks you to sort a linked list in O(n log n) time and O(1) space. Merge sort is the natural fit: use slow/fast to find the midpoint, recursively sort each half, then merge the two sorted halves.

def sort_list(head):
    if not head or not head.next:
        return head

    # Split at the midpoint
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None  # sever the first half

    left = sort_list(head)
    right = sort_list(mid)
    return merge(left, right)

def merge(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Note that fast starts at head.next rather than head. This ensures that for a two-node list, slow stays on the first node, giving us a clean split of one node per half.

Maximum Twin Sum of a Linked List

LeetCode 2130. Maximum Twin Sum of a Linked List defines the "twin" of node i as node (n - 1 - i) and asks for the maximum twin sum. This is another find-middle-then-reverse problem. Find the middle with slow/fast, reverse the second half, then walk both halves in tandem, tracking the maximum pairwise sum.

def pair_sum(head):
    # Find the middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half
    prev = None
    curr = slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # Walk both halves, track max sum
    max_sum = 0
    front, back = head, prev
    while back:
        max_sum = max(max_sum, front.val + back.val)
        front = front.next
        back = back.next
    return max_sum

Complexity

Most of these algorithms run in $O(n)$ time and $O(1)$ space. You are only reassigning existing next pointers and advancing a fixed number of local pointer variables. The exception is Sort List, which runs in $O(n \log n)$ time due to the recursive merge sort. The recursion also uses $O(\log n)$ stack space. Every other technique here uses a constant number of pointer variables that does not grow with the input size.

Recognizing this pattern

You're probably looking at pointer manipulation when:

• The input is a singly (or doubly) linked list and the problem demands $O(1)$ extra space, with no array conversion allowed.
• The transformation is structural: reverse, rotate, partition, reorder, or interleave nodes by rewiring next pointers.
• The problem says "in place" or "without using extra nodes" explicitly.
• The head itself may change, hinting that a dummy/sentinel node will simplify the code.

Common templates:

• prev/curr/next reversal: classic three-pointer reversal of a sublist or the whole list. Example: Reverse Linked List.
• Reverse in k-groups: count k nodes ahead, reverse the segment, splice back via a group-prev tail pointer. Example: Reverse Nodes in k-Group.
• Find middle + reverse second half + merge: splits the list into two and weaves them. Example: Reorder List.
• Two-list partition with dummies: walk once, append to "less" or "greater-equal" dummy chains, splice. Example: Partition List.
• Random pointer clone via interleaving: clone each node directly after its original, fix random pointers, then unzip. Example: Copy List with Random Pointer.