Linked Lists

When to Use

• Problem involves pointer manipulation (reversal, merging, cycle)
• O(1) space constraint — no converting to array
• Relative ordering of nodes matters, or need to process end-to-beginning

Signal phrases: "cycle", "middle", "kth from end", "reverse", "palindrome", "merge sorted", "reorder L0→Ln→L1", "copy with random pointer", "merge K sorted"

---

Pattern 1 — Fast & Slow Pointers (Floyd's)

Two pointers at different speeds. Slow=1 step, Fast=2 steps.

# LC 141 — Detect cycle
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# LC 876 — Middle of linked list
def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # slow lands at middle (or right-middle if even)

# LC 142 — Cycle entry point
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            slow = head    # reset one pointer to head
            while slow != fast:
                slow, fast = slow.next, fast.next
            return slow    # entry point
    return None

Use for: cycle detection, middle, kth from end, cycle entry point.

---

Pattern 2 — In-Place Reversal

Redirect next pointers without allocating new nodes. O(1) space.

# LC 206 — Reverse Linked List
def reverseList(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev    # reverse link
        prev = curr
        curr = next_node
    return prev   # new head

# LC 92 — Reverse sublist [left, right]
def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    pre = dummy
    for _ in range(left - 1):
        pre = pre.next
    curr = pre.next
    for _ in range(right - left):
        next_node = curr.next
        curr.next = next_node.next
        next_node.next = pre.next
        pre.next = next_node
    return dummy.next

Use for: reverse whole list, reverse sublist, palindrome check (reverse second half).

---

Pattern 3 — Dummy Node (Sentinel)

Placeholder node before head eliminates edge cases when head might change.

# Template — use whenever building or modifying from the front
dummy = ListNode(0)
curr = dummy

while condition:
    if some_logic:
        curr.next = new_node
        curr = curr.next

return dummy.next    # actual head

# LC 21 — Merge Two Sorted Lists
def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

Use for: merge sorted lists, remove node (head might be target), partition list.

---

Pattern 4 — Two-Pointer Gap (Fixed Distance)

Both pointers move at same speed, but one starts N steps ahead. When leader hits end, trailer is at target.

# LC 19 — Remove Nth Node from End
def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    left, right = dummy, head
    for _ in range(n):
        right = right.next       # create gap of N
    while right:
        left = left.next
        right = right.next       # move both until right hits None
    left.next = left.next.next   # remove target
    return dummy.next

# LC 160 — Intersection of Two Linked Lists
def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB    # switch lists when exhausted
        b = b.next if b else headA
    return a   # either intersection or None (both reach None together)

Use for: Nth from end, intersection of two lists.

---

Pattern 5 — In-Place Reordering (Composite)

Combines fast/slow + reversal + merge. Used when list must be rearranged without new nodes.

# LC 143 — Reorder List: L0→Ln→L1→Ln-1→...
def reorderList(head):
    # Step 1: Find middle
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next

    # Step 2: Reverse second half
    prev, curr = None, slow.next
    slow.next = None   # cut list at middle
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    second = prev

    # Step 3: Interleave merge
    first = head
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Use for: Reorder List #143, Reverse Nodes in k-Group #25 (harder variant).

---

Pattern 6 — Interweaving (Copy with Random Pointer)

Clone a list where each node has a random pointer. Three-step: interleave copies, assign randoms, separate.

# LC 138 — Copy List with Random Pointer — O(N) time, O(1) extra space
def copyRandomList(head):
    if not head:
        return None

    # Step 1: Interleave — A→A'→B→B'→C→C'
    curr = head
    while curr:
        clone = Node(curr.val, curr.next, None)
        curr.next = clone
        curr = clone.next

    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next   # clone's random = original's random's clone
        curr = curr.next.next

    # Step 3: Separate lists
    old = head
    new_head = head.next
    curr = new_head
    while old:
        old.next = curr.next           # restore original
        old = old.next
        if curr.next:
            curr.next = curr.next.next  # advance clone
            curr = curr.next

    return new_head

Key insight: After interleaving, curr.random.next is the copy of curr.random. This avoids a hashmap.

---

Pattern 7 — K-Way Merge (Heap)

Merge K sorted lists by maintaining a min-heap of current heads.

import heapq

# LC 23 — Merge K Sorted Lists
def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

Time: O(N log K), N = total nodes, K = number of lists.

---

Pattern 8 — Recursive Traversal (Backwards)

Call stack naturally gives you access to nodes in reverse order. Logic AFTER recurse(node.next) = post-order (tail to head).

# Template
def recurse(node):
    if not node:
        return
    # Logic here = PRE-ORDER (head to tail)
    recurse(node.next)
    # Logic here = POST-ORDER (tail to head) — stack "remembers" nodes for you

# LC 2 — Add Two Numbers (process digits from end)
# LC 206 — Reverse List (recursive version)
def reverseListRecursive(head):
    if not head or not head.next:
        return head
    new_head = reverseListRecursive(head.next)
    head.next.next = head   # reverse link
    head.next = None
    return new_head

Use when: need to process from tail first, "print in reverse", align digits from end.

---

Pattern Map

---

Senior Tips

• Always draw pointer state before/after each step
• Dummy node before head eliminates head-is-target edge case
• When using heap for K-Way merge, store (val, list_idx, node) — list_idx breaks val ties
• Interweaving is always O(1) space vs O(N) hashmap approach — know both

---

Related

• [[DSA/DSA Techniques for Interviews/02. Two Pointers]] — fast/slow is a linked-list variant
• [[DSA/DSA Techniques for Interviews/09. Heap & Priority Queue]] — K-way merge uses heap
• [[DSA/Data Structures/Linked List]] — data structure internals