Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 225 ยท Linked Lists

Linked List Problems

Solve classic linked list problems in Python, brute force first: palindrome list, intersection, add two numbers, random-pointer copy, reorder and LRU cache.

You now know the building blocks: dummy nodes, reversal, fast and slow pointers, merging. This lesson puts them to work on six problems that show up again and again in interviews and real code. For each one we start with the obvious brute-force idea, find what is wasteful about it, and then improve it, always stating the time and space cost.

All examples share this setup. Each TryIt repeats it so that every example runs on its own.

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

A good habit for every problem: ask what happens for an empty list, a one-node list and a list where the interesting node is the head or the tail.

Problem 1: Is the list a palindrome?

A palindrome reads the same forward and backward: 1 -> 2 -> 2 -> 1. A singly linked list cannot be read backward, which is exactly the difficulty.

Brute force. Copy the values into a Python list and compare it with its reverse. Time O(n), extra space O(n).

Better. Use three techniques in a row:

  1. Find the middle with slow/fast pointers.
  2. Reverse the second half in place.
  3. Walk the first half and the reversed second half together, comparing values.

Time O(n), extra space O(1). You may optionally reverse the second half back to restore the list.

TEXT
1 -> 2 -> 3 -> 2 -> 1
          ^ middle
second half reversed:  1 -> 2 -> 3 <- 2 <- 1
compare from both ends: 1=1, 2=2, done
Python Palindrome linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last printed value confirms that the list is back in its original order after the check. Note the tuple assignment head.next, prev, head = prev, head, head.next: the right side is evaluated completely before any assignment, so it is a safe one-line reversal step.

Problem 2: Intersection of two lists

Two lists may merge into a shared tail (the same node objects, not just equal values):

TEXT
A:  a1 -> a2 ---\
                 c1 -> c2 -> c3
B:  b1 -> b2 -> b3 /

Find the first shared node, or None.

Brute force. For each node in A, scan all of B for the same object. Time O(nยทm), space O(1).

Hash set. Put every node of A in a set, then walk B until a node is in the set. Time O(n + m), space O(n).

Two pointers swapping lists. Start pointer p on A and q on B. When one reaches the end, restart it on the other list's head. Both pointers then travel len(A) + len(B) steps in total, so they line up at the intersection (or both reach None together if there is none). Time O(n + m), space O(1). Intuition: the node counts before the shared part differ by len(A) - len(B); swapping heads cancels that difference.

Python Intersection of two linked lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the last test: equal values do not mean intersection. We compare nodes with is.

Problem 3: Add two numbers

Two non-negative integers are stored as lists with the least significant digit first: 342 is 2 -> 4 -> 3 and 465 is 5 -> 6 -> 4. Return their sum in the same format (807 is 7 -> 0 -> 8).

Brute force. Convert each list to an integer, add, and convert back. In Python this works because integers are unbounded, but it spends O(n) extra time and memory building a huge integer, and in languages with fixed-size ints it simply overflows. It also dodges what the problem is testing.

Digit-by-digit with a carry. This is addition on paper. Walk both lists at once, add the two digits plus the carry, store total % 10, and carry total // 10. The loop continues while either list has digits or there is a carry left. Time O(max(n, m)), extra space O(1) beyond the output.

Python Add two numbers stored as lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The or carry in the loop condition is what turns 999 + 1 into four digits ([0, 0, 0, 1]). Forgetting it is the number one bug on this problem.

Problem 4: Copy a list with random pointers

Each node has a next pointer and a random pointer to any node in the list (or None). Build a deep copy: all new nodes, with the same shape.

Hash map. First pass: create a copy of every node and store old -> new in a dict. Second pass: set copy.next = map[old.next] and copy.random = map[old.random]. Time O(n), space O(n).

Interleaving, O(1) extra space. Insert each copy right after its original (A -> A' -> B -> B' ...). Then every copy's random pointer is simply original.random.next. Finally split the two lists apart. It is a nice trick, but the map version is clearer and is the one to write first.

Python Copy list with random pointer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the interleaved version we must restore the original list in step 3. The final print confirms the original is unchanged.

Problem 5: Reorder list

Rearrange L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ... in place. For 1 2 3 4 5 the result is 1 5 2 4 3.

Brute force. Copy the nodes into an array, then use two indexes from the ends to relink. Time O(n), space O(n).

In place. Three techniques again: find the middle, reverse the second half, then weave the two halves together by alternating nodes. Time O(n), space O(1).

Python Reorder list in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop condition fast.next and fast.next.next stops slow on the first middle, so the first half is the longer one. That makes the weave loop end cleanly for both odd and even lengths.

Problem 6: LRU cache (preview)

An LRU (least recently used) cache holds at most capacity items. Reading or writing an item makes it the most recent; adding past capacity evicts the least recent. Both get and put must run in O(1).

Which structure does that? A dictionary finds an item in O(1), but cannot order by recency. A list orders items but moves in O(n). Combine them: a hash map from key to node and a doubly linked list ordered by recency. Moving a node to the front is O(1) because you hold the node and can unlink it directly, which is the superpower of the doubly linked list.

TEXT
dict:  key -> node
list:  head(dummy) <-> most recent <-> ... <-> least recent <-> tail(dummy)
get:   find node via dict, unlink it, insert after head
put:   same for existing keys; for new keys insert after head,
       and if over capacity remove the node before tail and its dict entry
Python LRU cache with dict and linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both get and put do a fixed number of pointer changes and dictionary operations, so each is O(1) time; space is O(capacity). The node stores its own key so that, when evicting, we know which dictionary entry to delete. Python's standard library also offers functools.lru_cache and collections.OrderedDict.move_to_end, but writing it once by hand is the best way to understand both.

More list exercises

Five smaller problems that combine the same pointer moves. In each one, draw the nodes on paper before you code, and re-link in an order that never loses the rest of the list.

  • Sublist search. Is list B a contiguous part of list A? The simple method tries every starting node of A and compares up to len(B) nodes: O(n * m). Because the nodes can only be followed forward, advanced matching such as KMP (see pattern matching) works by first copying the values into arrays.
  • Segregate even and odd. Keep two chains (evens and odds), append each node to the right chain in order, then join them. Two dummy heads make this stable, with O(n) time and O(1) extra space.
  • Delete N nodes after M nodes. Keep M, skip N, repeat to the end. It is a loop of "walk M, then cut N".
  • Rotate by k / reverse in blocks. Rotating right by k means making the list circular, then breaking it at the right place (n - k % n steps from the head). Reversing in groups of k reuses the reversal technique on each block and links the blocks together.
  • Multiply two numbers stored as lists. When digits are stored most significant first, build each integer by value = value * 10 + digit and multiply. In languages without big integers you would convert the lists into digit arrays and multiply them as in string multiplication.
Python Five list exercises, one runnable file

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reverse-in-groups version uses recursion on the remainder, so its depth is n / k; for very long lists convert it into a loop that tracks the previous group's tail. Rotation is the only one of the five that needs the length first, so it makes two passes.

Problem 7: Flatten a multilevel linked list

Each node has a next pointer and a child pointer. The child points to the head of another list, which may have children of its own. Flatten everything into one single-level list using only next. There are two natural orders, and interviewers ask for either one.

Depth-wise. A node's child list is placed right after the node, before the node's old next. This is a depth-first walk. A stack remembers where to resume: push the next node first, then the child, and pop the one visited next.

Level-wise. Walk the main list and, whenever you meet a child, append that whole child chain to the tail of the main list. Children of children end up even further back, so the result is in breadth-first order.

Python Flatten a multilevel list, two orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions are O(n) time for n nodes in total. The level-wise one needs no stack, only a tail pointer, so it uses O(1) extra space. The depth-wise one uses up to O(depth) stack space (a recursive version uses the same amount in the call stack). Set child to None as you go, or the flattened list will still contain stray child links.

Choosing a technique

Clue in the problem Reach for
"Middle", "half", "k-th from end" Fast/slow pointers or a gap
"Cycle", "loop" Floyd's algorithm
"Reverse", "palindrome", "reorder" Reverse the second half
"Merge", "combine sorted" Merge with a dummy
Head might be removed Dummy node
Need O(1) lookup plus ordering Hash map plus doubly linked list
Random pointers, graph-like links Hash map from old node to new node

Common mistakes

  • Comparing values when the problem means nodes. Intersection needs is.
  • Forgetting the carry when both lists are exhausted.
  • Not cutting the list in two before reversing the second half, which leaves a cycle in reorder.
  • Mutating the input (palindrome, copy) without restoring it, when the caller expects it unchanged.
  • Skipping edge cases: empty list, one node, two nodes, all-equal values.
  • Missing the key on LRU nodes, so eviction cannot remove the dictionary entry.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the extra space of the in-place palindrome check (middle, reverse second half, compare)?

    It only uses a few pointers. Reversing the second half is done in place by relinking nodes.
  2. 2. In the two-pointer intersection trick, why do both pointers meet at the intersection (or both reach None)?

    After switching lists, both pointers have walked the same total number of steps, so they reach the shared tail together.
  3. 3. Adding 999 and 1 stored as digit lists (least significant digit first). Which loop condition produces the correct four-digit result?

    After both lists end there may still be a carry, which becomes a new most significant digit.
  4. 4. Why does a node in an LRU cache store its key as well as its value?

    Eviction finds the oldest node from the list, then must remove the matching dictionary entry, so the node needs its key.
  5. 5. What is the time complexity of the hash-map solution for copying a list with random pointers?

    Two passes over the list, each node handled in constant time with dictionary lookups.

Summary

  • Most linked list problems combine a few moves: dummy node, reverse, fast/slow pointers, merge, and hash maps for lookup.
  • Palindrome list: middle, reverse second half, compare (O(n) time, O(1) space).
  • Intersection: compare nodes with is; the swap-heads trick is O(n + m) time and O(1) space.
  • Add two numbers: digit by digit with a carry, looping while either list or the carry remains.
  • Copy with random pointers: a map from old to new nodes (O(n) space) or interleaving (O(1) space).
  • Reorder list: middle, reverse the second half, weave.
  • LRU cache: hash map plus doubly linked list gives O(1) get and put.

Next: Stacks