Linked List Problems

Linked list problems are a composition of few ideas. You can decompose most questions into parts you already know how to write.

Using a Dummy Node

Removing the head, inserting before the head, returning an empty list will require an special checking of the edge case where the head may be empty. Using a dummy node eliminates edge cases involving the head node.

dummy = ListNode(0, head)
prev, cur = dummy, head
# ... do work ...
return dummy.next  # points to beginning of linked list

With this, you can always maintain the invariant prev.next == cur. This means removing cur is always just prev.next = cur.next, no need for special cases.

5 Common Operations

1 - Scan (traverse with prev/cur)

prev, cur = dummy, head
while cur:
    # process cur
    prev = cur
    cur = cur.next

2 - Remove cur

if want_to_remove(cur):
    prev.next = cur.next
    cur = cur.next        # prev stays

3 - Reverse a list

This operation does not use the dummy node. We initialise prev = None because the tail of the reversed list should point to nothing. Three pointers, one pass — at every step, cur.next is redirected to point backwards:

prev, cur = None, head
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
# prev is the new head

To reverse only a subrange (e.g. the second half after splitting), the same logic applies — just start cur at the subrange head and stop when cur reaches the boundary:

# Reverse from `start` up to (not including) `stop`
prev, cur = None, start
while cur != stop:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
# prev is the new head of the reversed segment

Time Complexity: O(n)
Space Complexity: O(1)

4 - Merge two sorted lists

Walk both lists simultaneously, always appending the smaller node to the result. After one list is exhausted, attach the remainder of the other:

dummy = ListNode()
tail = dummy
while l1 and l2:
    if l1.val <= l2.val:
        tail.next = l1
        l1 = l1.next
    else:
        tail.next = l2
        l2 = l2.next
    tail = tail.next
tail.next = l1 or l2
return dummy.next

Time Complexity: O(n + m)
Space Complexity: O(1) (re-links existing nodes)

5 - Find middle (fast/slow pointers)

The slow pointer advances one step while the fast pointer advances two. When fast reaches the end, slow is at the middle. Use fast = head.next to get the left-middle, which gives clean splits:

slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow = left-middle

→ 2             slow stops at 1  → halves: [1] and [2]
→ 2 → 3         slow stops at 2  → halves: [1,2] and [3]
→ 2 → 3 → 4     slow stops at 2  → halves: [1,2] and [3,4]
→ 2 → 3 → 4 → 5 slow stops at 3  → halves: [1,2,3] and [4,5]

Time Complexity: O(n)
Space Complexity: O(1)

Cycle detection & Floyd’s algorithm. For finding the entry point of a cycle, use slow = fast = head instead. Both pointers must start at the same node for the distance accounting in phase 2 to work:

# Phase 1: detect cycle
slow = fast = head       # must start at same node
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        break
else:
    return None  # no cycle

# Phase 2: find entry — F = kC - a, so both arrive at entry after F steps
slow2 = head
while slow2 != slow:
    slow2 = slow2.next
    slow = slow.next
return slow  # cycle entry node

Extra Trick: Two Dummy Nodes

For partition / split problems (e.g. “partition list around value x”), use two dummy nodes and route each node to one of them:

d1, d2 = ListNode(), ListNode()
t1, t2 = d1, d2
cur = head
while cur:
    if cur.val < x:
        t1.next = cur
        t1 = t1.next
    else:
        t2.next = cur
        t2 = t2.next
    cur = cur.next
t2.next = None          # terminate second list
t1.next = d2.next       # connect the two lists
return d1.next

This generalises to any problem where nodes must be separated into groups and optionally reconnected.

Decomposing Problems Into Blocks

Most linked list problems are just a composition of the blocks above:

Problem	Decomposition
Reverse Linked List	Reverse
Merge Two Sorted Lists	Merge
Linked List Cycle	Fast/slow (`slow == fast` → cycle)
Remove Nth From End	Dummy + scan with n-gap + Remove
Remove Duplicates (Sorted)	Dummy + scan + Remove when duplicate found
Reorder List	Fast/slow (split) → Reverse (2nd half) → interleave
Sort List	Fast/slow (split) + recurse + Merge = merge sort
Merge K Lists	Merge repeatedly (or with a heap)
Partition List	Two dummy nodes trick

The following worked examples show how these compositions look in practice.

Reverse Linked List 🔗

A direct application of Reverse:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

Time Complexity: O(n)
Space Complexity: O(1)

Remove Nth Node From End 🔗

Use the n-gap two-pointer trick: advance right by n steps first, then walk both left and right together. When right reaches the end, left is just before the target node.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        left, right = dummy, head

        # Create n-gap
        for _ in range(n):
            right = right.next

        # Walk until right hits the end
        while right:
            left = left.next
            right = right.next

        # left is now just before the target — Remove
        left.next = left.next.next
        return dummy.next

Time Complexity: O(n)
Space Complexity: O(1)

The dummy node is essential here — without it, removing the head itself (e.g. a single-element list with n=1) requires special-casing.

Linked List Cycle 🔗

A direct application of Fast/slow. If the fast pointer ever meets the slow pointer, a cycle exists:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Time Complexity: O(n)
Space Complexity: O(1)

Follow-up — finding the cycle start: once slow and fast meet, reset one pointer to head and advance both one step at a time. They will meet at the cycle’s entry point. This is Floyd’s algorithm.

Reorder List 🔗

This is a clean three-step composition:

Fast/slow — find the middle to split the list into two halves.
Reverse — reverse the second half.
Interleave — merge the two halves by alternating nodes.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # 1. Find middle (Fast/slow)
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None  # cut the list

        # 2. Reverse second half (Reverse)
        prev, cur = None, second
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        second = prev

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

Time Complexity: O(n)
Space Complexity: O(1)

Merge K Sorted Lists 🔗

Two approaches, both built on Merge:

Approach 1 — Divide and conquer. Repeatedly merge pairs of lists, halving the number of lists each round (like merge sort):

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(self.merge(l1, l2))
            lists = merged
        return lists[0]

    def merge(self, l1, l2):  # Merge
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Time Complexity: O(n log k) where n is total nodes and k is number of lists
Space Complexity: O(1) (ignoring the merged bookkeeping)

Approach 2 — Heap. Push the head of each list into a min-heap, then repeatedly pop the smallest and push its successor. This is a natural combination with the Heap/Priority Queue notes:

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy
        heap = []

        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        while heap:
            val, i, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

Time Complexity: O(n log k)
Space Complexity: O(k) for the heap

Sort List 🔗

Merge sort on a linked list: split with Fast/slow, recurse on both halves, merge with Merge. Linked lists are naturally suited to merge sort because the split and merge operations are both O(1) space.

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Split (Fast/slow)
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None

        # Recurse
        left = self.sortList(head)
        right = self.sortList(mid)

        # Merge
        dummy = ListNode()
        tail = dummy
        while left and right:
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        tail.next = left or right
        return dummy.next

Time Complexity: O(n log n)
Space Complexity: O(log n) for recursion stack