Pointer choreography, without the segfaults

What This Is

A placeholder node with value 0 (or any sentinel) that sits before the actual head. It exists solely to simplify code: you don't have to special-case "what if I need to modify the head?"

Why Use It

Without a dummy, merging two lists requires special logic for the first node (you might be setting the new head). With a dummy, the head is treated like any other node — all logic goes through the same path.

The Pattern

dummy = ListNode(0)
curr = dummy
# ... do work, attaching to curr.next ...
return dummy.next    # Skip the dummy, return the real head

When to Use

• Merging lists
• Modifying the head (reverse, reorder, etc.)
• Building a new list by attaching nodes

What This Is

Two pointers moving at different speeds (usually 1x and 2x). They're used to detect cycles (if they collide, there's a cycle) or find the middle of a list (slow reaches middle when fast reaches end).

Floyd's Cycle Detection

If there's a cycle, fast will eventually lap slow. The math: in a cycle of length C, fast gains 1 node on slow each iteration. After C iterations, they collide. This is guaranteed to happen before traversing n nodes.

The Pattern

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True  # Cycle detected
return False  # No cycle

Finding the Middle

Run the same loop until fast reaches the end. When it does, slow is at the middle. Use this for: splitting lists, finding palindromes, or finding the start of a cycle.

When to Use

• Detect cycles (Floyd's algorithm)
• Find the middle of a list
• Find the start of a cycle (combine with other techniques)
• Palindrome detection (reverse second half)

⚠️ Gotchas

• Boundary check: while fast and fast.next — without this, fast.next.next will crash if fast is null.
• Slow and fast might not collide at the exact same node in all cases, but will collide if a cycle exists.
• Use is or === for pointer equality, not value equality.

What This Is

Changing the direction of pointers to reverse a list (or a portion of it). Maintain three pointers: prev, curr, next. At each step, reverse the pointer and move forward.

Why It's Needed

You can't iterate backwards in a singly linked list. To check if a list is a palindrome, extract the second half, reverse it, and compare. To reverse a list, you flip all pointers.

The Pattern

prev, curr = None, head
while curr:
    next = curr.next      # SAVE next before breaking link
    curr.next = prev      # Reverse the pointer
    prev = curr           # Move prev forward
    curr = next           # Move curr forward
return prev               # New head

Key Insight

next = curr.next MUST come before curr.next = prev. Otherwise, you lose access to the rest of the list.

When to Use

• Reverse a list (or a portion of it)
• Palindrome detection (reverse second half, then compare)
• Reordering nodes (e.g., reverse nodes in k-groups)

⚠️ Gotchas

• Forgetting to save next → infinite loop or lost nodes.
• Wrong initial value for prev: it should be None, not head.
• Returning the wrong pointer: return prev, not head (head is now the tail).

What This Is

Two pointers tracking different positions in the same list (or different lists). Used for finding kth elements, splitting lists, or merging sorted lists.

Find Kth Node From End

Advance first pointer k steps. Then advance both until first reaches the end. Second pointer is now at the kth from end.

The Pattern

# Find kth from end
first, second = head, head
for _ in range(k):
    first = first.next  # Advance first k steps

while first.next:       # Stop when first is at end
    first = first.next
    second = second.next

# second is now kth from end
return second

When to Use

• Find kth element from the end
• Remove kth node
• Split list at a position
• Merge two sorted lists (iterating both lists in parallel)