Linked Lists cheatsheet

🔗 Linked Lists

Hold pointers, not indexes: rewire `next` in place, use a dummy head for edge cases, and two runners for middles, cycles and gaps.

Study the unit Practice this pattern

Recognize the pattern

Reverse a list or part of it, in place → three pointers (prev, cur, nxt)
The head might be deleted or replaced → dummy head, return dummy.next
Find the middle in one pass → fast (2 steps) & slow (1 step)
Does it loop? Where does the loop start? → Floyd's tortoise and hare
Nth node from the end in one pass → two pointers n apart
Combine sorted lists → dummy + tail pointer merge (k lists → heap)
Rearrange / palindrome check → split at middle, reverse 2nd half, weave or compare

Dummy head

A fake node before the head gives every real node a predecessor. Build or edit after it, then return dummy.next.

Python template

def remove_value(head: ListNode | None, target: int):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next  # delete
        else:
            prev = prev.next
    return dummy.next

Reverse in place

Python template

def reverse(head: ListNode | None) -> ListNode | None:
    prev, cur = None, head
    while cur:
        nxt = cur.next    # save the rest
        cur.next = prev   # flip
        prev, cur = cur, nxt
    return prev           # new head

Fast & slow: middle and cycle

while fast and fast.next stops on the second middle; while fast.next and fast.next.next on the first (use it to split).

Python template

def middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Gap of n: nth from the end

Python template

def remove_nth_from_end(head, n: int):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next  # slow is before it
    return dummy.next

Merge two sorted lists

Python template

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

Split, reverse, weave

Find the first middle, cut with slow.next = None, reverse the second half, then interleave (Reorder List) or compare (Palindrome).

Python template

def split_reverse(head):
    slow = fast = head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None  # cut
    prev = None
    while second:
        second.next, prev, second = prev, second, second.next
    return head, prev  # first half, reversed 2nd

Operation costs

Operation	Time	Space
Access / search by position or value	O(n)	O(1)
Insert / delete after a node you hold	O(1)	O(1)
Insert at head	O(1)	O(1)
Reverse (iterative)	O(n)	O(1)
Reverse (recursive)	O(n)	O(n) stack
Middle / cycle check (fast & slow)	O(n)	O(1)
Merge two sorted lists	O(n + m)	O(1)

Watch for

Overwriting cur.next before saving it: the rest of the list is lost.
Returning the old head after a reversal: it's the tail now; return prev.
Forgetting dummy.next (returning dummy adds a fake 0 at the front).
Calling fast.next.next without checking fast and fast.next first → AttributeError on None.
Not cutting a list when splitting (slow.next = None), which creates a cycle after reordering.
Comparing nodes with == on values instead of is when checking whether two pointers meet.