Linked list basics — reverse, cycle detection, merge

Linked-list problems are about pointer manipulation in Python. Real codebases rarely use them (Python’s list is a dynamic array, deque covers queues), but they’re staple interview fodder for reasoning about pointers.

Setup

from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    next: Optional["Node"] = None

Pattern: reverse a linked list

def reverse(head: Node | None) -> Node | None:
    prev = None
    curr = head
    while curr:
        next_ = curr.next         # save
        curr.next = prev          # reverse pointer
        prev = curr               # advance prev
        curr = next_              # advance curr
    return prev

Three-pointer dance: prev, curr, next_. After loop, prev is the new head.

Recursive version:

def reverse_rec(head: Node | None) -> Node | None:
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

Iterative is preferred — recursive uses O(n) stack and risks stack overflow on long lists.

Pattern: cycle detection (Floyd’s algorithm)

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

Two pointers, fast moves twice as fast. If there’s a cycle, fast eventually laps slow. If no cycle, fast hits None.

To find the cycle’s start:

def cycle_start(head: Node | None) -> Node | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Reset slow to head; both move at same speed; meet at cycle start
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Math: when slow and fast meet inside the cycle, the distance from head to cycle-start equals the distance from meet-point to cycle-start (modulo cycle length).

Pattern: merge two sorted lists

def merge(a: Node | None, b: Node | None) -> Node | None:
    dummy = Node(0)
    tail = dummy
    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 the rest
    return dummy.next

The dummy node trick: keeps the head-handling code uniform. Without it you’d need a special case for “first node.”

Pattern: find middle node

def middle(head: Node | None) -> Node | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

When fast reaches the end, slow is at the middle. For even-length lists, returns the second of the two middles.

Pattern: remove Nth from end

def remove_nth_from_end(head: Node | None, n: int) -> Node | None:
    dummy = Node(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        if not fast:
            return head    # n too large
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

Two pointers, gap of n+1. When fast hits None, slow is right before the target.

Problem: reverse list in groups of K

def reverse_k_group(head: Node | None, k: int) -> Node | None:
    # Check if at least k nodes remain
    node = head
    for _ in range(k):
        if not node:
            return head
        node = node.next
    
    # Reverse first k nodes
    prev = None
    curr = head
    for _ in range(k):
        next_ = curr.next
        curr.next = prev
        prev = curr
        curr = next_
    
    # head is now the tail of the reversed group; recurse on the rest
    head.next = reverse_k_group(curr, k)
    return prev

Pitfalls

• Forgetting to save next before overwriting curr.next — loses the rest of the list.
• Comparing nodes with == vs is — is for identity (same node), == for value equality (and only if __eq__ is defined).
• Off-by-one in two-pointer gaps — draw a small example to verify.
• Returning head instead of dummy.next when using a dummy — head may have moved or been removed.

Interview angle

• “Reverse a linked list.” - iterative with three pointers (prev, curr, next), O(n) time and O(1) space. Say the recursive version exists but costs O(n) stack, which matters on long lists.
• “Detect a cycle.” - Floyd’s tortoise and hare: slow moves one, fast moves two; they meet inside a cycle. O(1) space, versus a hash set’s O(n).
• “Find where the cycle starts.” - after they meet, reset one pointer to the head and advance both one step at a time; they meet at the cycle entrance. Being able to state that as a known result is enough.
• “Why a dummy head node?” - it removes the special case where the operation modifies the first node, so insertion and deletion have one uniform code path. Most off-by-one linked-list bugs come from omitting it.