Linked Lists

Linked list problems test whether you can manipulate pointers carefully without losing track of nodes. The data structure is simple. The difficulty is in the order of operations: one wrong assignment and the rest of the list is gone. The reliable approach is to draw the nodes, name your pointers, and use a handful of standard techniques: a dummy head, fast and slow pointers, and reversal.

1. The structure

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

def build(values):
    """Helper for tests: build a list from a Python list and return the head."""
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

assert to_list(build([1, 2, 3])) == [1, 2, 3]
assert to_list(build([])) == []

Access by index costs $O(n)$, and insertion or deletion at a known node costs $O(1)$. Compared with an array, you give up random access to gain cheap splicing.

2. Techniques you need

The dummy head

Many edge cases arise because the head might change. A dummy node placed before the head means every real node has a predecessor, so inserting or deleting at the front is the same code as anywhere else. Return dummy.next at the end.

Draw before you code

Sketch the nodes and arrows. Name each pointer (prev, curr, nxt). Write the assignments in the order that never loses a reference: save the next node before overwriting next.

Fast and slow pointers

Move one pointer one step and another two steps. They reveal the middle (when the fast one ends, the slow one is in the middle) and cycles (the fast one eventually laps the slow one).

Reversal

Reversing a list is a building block for many harder problems.

3. Reverse a linked list

Walk the list, redirecting each node's next to point backward.

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next          # 1. remember the rest
        curr.next = prev         # 2. point backward
        prev = curr              # 3. advance prev
        curr = nxt               # 4. advance curr
    return prev                  # prev is the new head

assert to_list(reverse_list(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse_list(build([1]))) == [1]
assert to_list(reverse_list(build([]))) == []

Time $O(n)$, space $O(1)$. The recursive version is shorter and uses $O(n)$ stack:

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head        # the node after head now points back at head
    head.next = None
    return new_head

assert to_list(reverse_list_recursive(build([1, 2, 3]))) == [3, 2, 1]

Reverse a sublist between positions left and right (1-indexed): walk to the node before left, then reverse right - left + 1 nodes by repeatedly moving the next node to the front of the segment.

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    curr = before.next                    # first node of the segment
    for _ in range(right - left):
        moved = curr.next                 # take the node after curr ...
        curr.next = moved.next
        moved.next = before.next          # ... and put it at the front of the segment
        before.next = moved
    return dummy.next

assert to_list(reverse_between(build([1, 2, 3, 4, 5]), 2, 4)) == [1, 4, 3, 2, 5]
assert to_list(reverse_between(build([5]), 1, 1)) == [5]

4. Merge two sorted lists

Use a dummy head and a tail pointer, always appending the smaller front node.

def merge_two_lists(a, b):
    dummy = ListNode()
    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                    # append whichever list remains
    return dummy.next

assert to_list(merge_two_lists(build([1, 2, 4]), build([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert to_list(merge_two_lists(build([]), build([0]))) == [0]

Time $O(n+m)$, space $O(1)$. This is also the merge step of merge sort on a list, and the building block for merging $k$ lists with a heap (see the heaps chapter).

5. Fast and slow pointers

Find the middle. When fast reaches the end, slow is at the middle (the second middle for even lengths).

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

assert middle_node(build([1, 2, 3, 4, 5])).val == 3
assert middle_node(build([1, 2, 3, 4])).val == 3

Detect a cycle (Floyd's tortoise and hare). If there is a cycle, the fast pointer eventually catches the slow one inside it. If not, fast reaches the end.

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

a = build([1, 2, 3, 4])
assert has_cycle(a) is False
tail = a
while tail.next:
    tail = tail.next
tail.next = a.next                  # create a cycle back to the second node
assert has_cycle(a) is True

Find where the cycle begins. After the pointers meet, reset one pointer to the head. Move both one step at a time. They meet at the cycle's entry. (The distance from the head to the entry equals the distance from the meeting point to the entry, going around the cycle, so the two walks align.)

def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

b = build([3, 2, 0, -4])
entry = b.next
tail = b
while tail.next:
    tail = tail.next
tail.next = entry
assert detect_cycle_start(b) is entry
assert detect_cycle_start(build([1, 2])) is None

Time $O(n)$, space $O(1)$. The hash set alternative uses $O(n)$ space, so say that Floyd's algorithm is the constant-space answer.

6. Remove the $n$th node from the end

Use two pointers that start $n$ apart. When the front reaches the end, the back is just before the node to delete. A dummy head handles removing the first node.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):                 # advance fast by n
        fast = fast.next
    while fast.next:                   # move both until fast is on the last node
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next         # delete the target
    return dummy.next

assert to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert to_list(remove_nth_from_end(build([1]), 1)) == []
assert to_list(remove_nth_from_end(build([1, 2]), 2)) == [2]

7. Palindrome list and reorder list

These combine the techniques: find the middle, reverse the second half, then walk both halves together.

def is_palindrome_list(head):
    slow = fast = head
    while fast and fast.next:                 # find the middle
        slow = slow.next
        fast = fast.next.next
    prev = None
    while slow:                               # reverse the second half
        nxt = slow.next
        slow.next = prev
        prev, slow = slow, nxt
    left, right = head, prev
    while right:                              # compare the two halves
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

assert is_palindrome_list(build([1, 2, 2, 1])) is True
assert is_palindrome_list(build([1, 2, 3, 2, 1])) is True
assert is_palindrome_list(build([1, 2])) is False

This uses $O(1)$ extra space but modifies the list. In an interview, mention whether you restore it, or state that the problem allows modification.

8. Add two numbers stored as lists

Digits are stored in reverse order. Add digit by digit with a carry, using a dummy head.

def add_two_numbers(a, b):
    dummy = ListNode()
    tail, carry = dummy, 0
    while a or b or carry:
        total = carry + (a.val if a else 0) + (b.val if b else 0)
        carry, digit = divmod(total, 10)
        tail.next = ListNode(digit)
        tail = tail.next
        a = a.next if a else None
        b = b.next if b else None
    return dummy.next

assert to_list(add_two_numbers(build([2, 4, 3]), build([5, 6, 4]))) == [7, 0, 8]
assert to_list(add_two_numbers(build([9, 9]), build([1]))) == [0, 0, 1]

9. LRU cache: a linked list plus a hash map

Design a cache with get and put in $O(1)$, evicting the least recently used entry when full. The standard answer combines a hash map (key to node, for $O(1)$ lookup) with a doubly linked list ordered by recency (for $O(1)$ move-to-front and eviction from the back). Sentinel head and tail nodes remove edge cases.

class DNode:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head, self.tail = DNode(), DNode()      # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)                        # now the most recently used
        return node.val

    def put(self, key, val):
        if key in self.map:
            self._remove(self.map[key])
        node = DNode(key, val)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev                     # least recently used
            self._remove(lru)
            del self.map[lru.key]

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)                                          # evicts key 2
assert c.get(2) == -1
c.put(4, 4)                                          # evicts key 1
assert c.get(1) == -1 and c.get(3) == 3 and c.get(4) == 4

In Python you can also use collections.OrderedDict with move_to_end and popitem(last=False), which is acceptable, but be ready to implement the linked-list version, because interviewers often ask for it.

10. Common mistakes

• Losing the rest of the list by overwriting next before saving it.
• Forgetting the dummy head and writing separate code for the head case.
• Not handling empty and single-node lists, which are the usual tests.
• Off-by-one in the two-pointer gap for "$n$th from the end".
• Infinite loops from accidental cycles when you forget to set the last next to None after splitting a list.
• Comparing nodes by value instead of identity (is) when detecting cycles.
• Modifying the input when the problem implies you should not. Ask.
• Recursion depth. A recursive reversal of a very long list can exceed Python's recursion limit, so mention the iterative version.

11. Practice set

1. Reverse linked list, reverse linked list II, reverse nodes in $k$-group.
2. Merge two sorted lists, merge $k$ sorted lists.
3. Linked list cycle, linked list cycle II, find the duplicate number.
4. Middle of the linked list, palindrome linked list.
5. Remove nth node from end, remove duplicates from sorted list.
6. Reorder list (middle, reverse second half, interleave).
7. Add two numbers, add two numbers II.
8. Copy list with random pointer.
9. LRU cache, LFU cache.
10. Intersection of two linked lists.