AlgoScope

Linked List Algorithms

Nodes joined by pointers, where every operation comes down to which arrow you move first.

18 topics5 lessons1 families

A linked list stores each value in its own node with a pointer to the next one. Nothing is contiguous, so there is no index arithmetic: reaching the tenth node means following nine pointers. In exchange, putting a node in or taking one out is a couple of pointer writes, and nothing after it moves.

That trade shapes every algorithm here. Since you cannot jump, you carry extra pointers instead: a trailing pointer to relink behind you, a second pointer running at twice the speed to find the middle or a cycle, a pointer held n nodes ahead so the gap itself marks the node to remove. One pass, O(1) extra memory, and no index anywhere.

The cost is that the order of assignments matters. A node you unlink is unreachable unless you saved it first, and a good half of the bugs in this category are one line written before another rather than after it.

After this you can

  • Insert and delete at the head, the tail and the middle, and say what each one costs
  • Reverse a list in one pass with three pointers, and say why three are needed
  • Use a fast and a slow pointer to find the middle, detect a cycle and locate where it starts
  • Rewire a list in place, reordering, rotating or reversing it in blocks of k, with no second list
5✓1✓4✓2headcurr

Visit 2. Its next is null: the end.

Open in the player →or start at step 5

In this order

  1. TraversalFollow next pointers from head until null.
  2. Insert at HeadPoint the new node at the old head, then move head onto it. Nothing else shifts.
  3. Insert at TailWalk to the last node and attach the new node after it.
  4. Insert at PositionWalk to the node before the gap, then relink it and the new node in order.
  5. Delete NodeRoute the predecessor's pointer around the node, then drop it.
  6. Reverse Linked ListWalk the list with three pointers and flip each arrow to face the other way.
  7. Intersection of Two ListsWalk pa down A then B and pb down B then A; they meet at the shared node after the same distance, or at null together.
  8. Fast and Slow PointersOne pointer moves twice as fast as the other. Finds middles and cycles in one pass.
  9. Find MiddleSlow moves one, fast moves two. When fast runs out, slow is halfway.
  10. Detect CycleIf fast ever lands on slow, the list loops. On a straight list fast just runs out.
  11. Find Cycle EntryAfter they meet, restart one at the head and walk both by one. They meet again at the entry.
  12. Remove CycleAfter slow and fast meet, walk from the head and the meeting point to the entry, then once round the loop to cut the arrow before it.
  13. Remove Nth From EndLead one pointer n ahead, then walk both until the leader runs out. Trail is just before the target.
  14. Merge Two Sorted ListsRepeatedly take the smaller head and hang it on the merged tail; relink instead of copying.
  15. Merge K Sorted ListsKeep the current heads in a min-heap so the global smallest is always one pop away.
  16. Palindrome Linked ListMiddle by slow and fast, reverse the second half, compare front against back, reverse it back.
  17. Reorder ListMiddle by slow and fast, reverse the second half, weave first and second alternately.
  18. Reverse in Groups of kCount k ahead, reverse that run with prev and curr, hook the previous group's tail onto the new front.
  19. Rotate ListClose the list into a ring through the tail, then cut it n - k mod n steps in.

Where people go wrong

Losing the rest of the list

In a reversal, overwriting current.next before saving it makes everything after the current node unreachable. Save the successor first, then flip the arrow, then advance.

The head is its own case

Inserting before the head or deleting it changes the pointer the caller holds, so every function needs a branch for it. A dummy node in front of the list removes the branch entirely, and you return dummy.next at the end.

Stepping off the end with the fast pointer

A fast pointer moves two nodes per step, so the loop condition has to check both fast and fast.next. Checking only one crashes on lists of even length, and on cycles it is the check that never fires.

Or a different category

Array Algorithms and Techniques

You read by position far more often than you insert, or you want the values next to each other in memory.

Data Structures

You want the variants themselves: doubly linked, circular, skip list, and what each one adds.

Lessons that teach these