Linked List Algorithms
Nodes joined by pointers, where every operation comes down to which arrow you move first.
Singly Linked List: Traverse
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
In this order
- Traversal
- Insert at Head
- Insert at Tail
- Insert at Position
- Delete Node
- Reverse Linked List
- Intersection of Two Lists
- Fast and Slow Pointers
- Find Middle
- Detect Cycle
- Find Cycle Entry
- Remove Cycle
- Remove Nth From End
- Merge Two Sorted Lists
- Merge K Sorted Lists
- Palindrome Linked List
- Reorder List
- Reverse in Groups of k
- Rotate List
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.