Linked Lists — Reverse, Merge, and the Fast & Slow Pointer Trick

A linked list is a chain of nodes. Each node holds a value and a pointer (next) to the following node. Unlike an array, the nodes are scattered in memory, so you can't jump to the 5th element directly — you walk from the head.

head → [3] → [8] → [1] → [6] → None

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

class ListNode {
    int val; ListNode next;
    ListNode(int val) { this.val = val; }
}

Operation	Array	Linked list
Access k-th element	O(1)	O(k)
Insert/delete at the front	O(n)	O(1)
Insert/delete after a known node	O(n)	O(1)

Linked-list questions are mostly about pointer manipulation without losing track of nodes. Draw boxes and arrows on paper — seriously, every strong candidate does this.

Technique 1 — Reverse a linked list (the most asked)

Walk the list and flip each next pointer to point backwards. You need three references: prev, cur, and a saved nxt (so you don't lose the rest of the list).

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 1. save the rest
        cur.next = prev     # 2. flip the arrow
        prev = cur          # 3. move prev forward
        cur = nxt           # 4. move cur forward
    return prev             # new head

ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

Dry run on 1 → 2 → 3:

step	prev	cur	list so far
start	None	1
1	1	2	1 → None
2	2	3	2 → 1 → None
3	3	None	3 → 2 → 1 → None ✓

O(n) time, O(1) space. Reversal is a building block for Palindrome Linked List, Reorder List and Reverse Nodes in k-Group.

Technique 2 — Fast & slow pointers

Move slow one step and fast two steps at a time.

Middle of the list: when fast reaches the end, slow is in the middle.

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Detect a cycle (Floyd's algorithm): if there is a loop, the fast pointer eventually laps the slow one and they meet. If fast reaches None, there's no cycle.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

O(n) time and O(1) space — better than storing visited nodes in a set.

Technique 3 — The dummy (sentinel) node

When the head itself might change (deleting it, merging lists), create a fake node in front. Then every real node has a predecessor, and you return dummy.next at the end — no special cases.

Merge Two Sorted Lists:

def merge_two_lists(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       # attach whatever is left
    return dummy.next

Technique 4 — Two pointers with a gap

Remove the N-th node from the end in one pass: move fast N steps ahead, then move both until fast reaches the end. Now slow is just before the node to delete. Start both at a dummy node so removing the head also works.

def remove_nth_from_end(head, n):
    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      # skip the target
    return dummy.next

Technique 5 — Combine the techniques

• Palindrome Linked List: find the middle (fast/slow) → reverse the second half → compare both halves.
• Reorder List (L0 → Ln → L1 → Ln−1 …): find middle → reverse second half → merge alternately.
• Intersection of Two Lists: walk both; when one reaches the end, jump to the other list's head. They meet at the intersection (or both reach None).

How to recognise linked-list patterns

Need	Technique
reverse all or part	prev / cur / nxt reversal
middle, cycle, k-th from end	fast & slow / gap pointers
head may change, merging	dummy node
palindrome, reorder	middle + reverse + merge

Common mistakes

1. Losing the rest of the list — always save cur.next before changing it.
2. NullPointerException / AttributeError: check fast and fast.next before fast.next.next.
3. Forgetting to return the new head after reversing.
4. Special-casing the head instead of using a dummy node.

Key takeaways

• Draw it. Linked-list bugs are pointer bugs.
• Master reversal and fast & slow — together they solve most questions in O(n) time and O(1) space.
• A dummy node removes edge cases when the head can change.