Two Pointers on Linked Lists: Remove Nth Node, Palindrome, Reorder

Two pointers on a linked list is a different animal from two pointers on an array. For months I solved the array versions easily, then froze the moment the input was a linked list. Same idea, but the missing piece was random access, and that changed how the pointers move.

This post walks through three of the most common two pointers linked list problems on LeetCode: remove the Nth node from the end, check if a list is a palindrome, and reorder a list in place. Different questions, same two moves underneath.

Why linked lists change the game

On an array you can jump anywhere. Want the element five slots from the end? Subtract five from the length and index straight there. The opposite-ends pattern from the two pointer deep dive leans on that freedom.

A singly linked list takes it away. You cannot reach position k without walking there one step at a time, and you cannot step backward at all. So you use a second pointer to encode position for you, measuring distance and finding the middle without knowing the length up front. The two moves that fall out of this are the offset pointer and the fast and slow pointer.

Move one: the offset pointer, for Remove Nth Node From End of List

The naive approach to remove nth node from end of list is two passes: traverse the list once for its length L, then walk again to node L minus N. One pass is cleaner. Keep a fixed gap of N nodes between two pointers: advance a lead pointer N steps ahead, then move both forward together. When the lead falls off the end, the trailing pointer sits exactly N nodes from the end, right before the node you remove.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)   # guards against removing the head itself
    lead = trail = dummy
    for _ in range(n):
        lead = lead.next        # open a gap of n nodes
    while lead.next:
        lead = lead.next
        trail = trail.next      # move together, preserving the gap
    trail.next = trail.next.next  # unlink the target
    return dummy.next

The dummy node in front of the head is not decoration. Without it, removing the first node is a special case with no previous node to reattach. I also stop on lead.next, not lead, so trail lands on the node before the target. Off-by-one bugs here are the most common way this breaks, so trace a two-node list by hand before trusting it.

Move two: fast and slow, for Palindrome Linked List

For palindrome linked list you cannot walk inward, because a singly linked list has no backward step. The plan has three phases: find the middle, reverse the second half, then compare the halves node by node. Finding the middle uses the fast and slow trick, the same family behind detecting a cycle in a linked list. Both pointers start at the head; fast moves two nodes for every one slow moves, so when fast reaches the end, slow is at the middle.

def is_palindrome(head):
    slow = fast = head          # phase 1: slow lands on the middle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None                 # phase 2: reverse the second half
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev    # phase 3: walk inward from both ends
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

Fast covers twice the ground, so by the time it finishes the list, slow has covered half. For an odd length slow stops on the center; for an even length it stops on the first node of the second half. The comparison loop runs on while right because the reversed half is never longer than the first half, so it is the safe one to exhaust.

Move three: combining both, for Reorder List

Reorder List (LeetCode 143) uses every idea at once. You rearrange L0 to L1 to ... to Ln into L0, Ln, L1, Ln-1, ... by relinking nodes, not copying values. The elegant in-place answer: find the middle, reverse the second half, then merge the two halves by alternating.

def reorder_list(head):
    if not head or not head.next:
        return
    slow = fast = head          # find middle with fast and slow
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next          # reverse the second half
    slow.next = None
    prev = None
    while second:
        second.next, prev, second = prev, second, second.next
    second = prev
    first = head                # merge, alternating
    while second:
        first.next, first = second, first.next
        second.next, second = first, second.next

It is the same toolkit as the palindrome problem, rearranged: fast and slow to find the middle, the standard reverse-in-place loop, then a merge instead of a comparison. Once you internalize "find middle, reverse tail, do something pairwise," a whole category of problems collapses into one template.

The two moves, side by side

• A node a fixed distance from the end: offset pointer, open a gap of k then move both together.
• The middle of the list: fast and slow, fast moves 2x and slow lands on the middle.
• Compare or interleave two halves: fast and slow then reverse, split at the middle and reverse the tail.
• Loop or cycle detection: fast and slow, fast laps slow if a cycle exists.

The unifying insight is that a linked list denies you random access, so a second pointer becomes your ruler. It measures a fixed offset for Remove Nth Node, and the halfway mark for palindrome and reorder. You never count the length; the geometry of the two pointers counts it for you.

Bugs that got me every time

Any time a solution might touch or remove the head, front the list with a dummy so the head is not a special case. Off-by-one in the offset loop is the other recurring one: advancing the lead pointer N versus N plus one times decides whether trail lands on the target or the node before it. For fast and slow, decide up front whether slow stops on the exact center or the start of the second half, then match your loop condition, since the wrong one silently shifts your middle by a node.

How this connects to the array pattern

If you read the sliding window versus two pointers breakdown, you know two pointers is a family, not a single trick. On sorted arrays they converge from opposite ends; on linked lists they chase each other in the same direction because you can only move forward. Same core idea, adapted to what the data structure allows.

I have been working through the two pointer track on Levelop, and linked list problems forced me to stop memorizing solutions and understand why the pointers move the way they do.