Linked Lists

A linked list is a chain of nodes where each node holds a value and a pointer to the next node, so you can insert or remove at a known position in O(1) but must walk O(n) to reach the k-th item.

Walk the list once with three pointers (prev, cur, next) and flip each node's next pointer to point backwards, reversing the list in O(n) time and O(1) space.

Move a slow pointer one step and a fast pointer two steps: if they meet there is a cycle, and when the fast one reaches the end the slow one is at the middle, all in O(n) time and O(1) space.

Merge two sorted lists by repeatedly attaching the smaller head to a growing tail, split a list at its middle with fast and slow pointers, and combine the two to merge sort a linked list in O(n log n).

Put a fake node in front of the real head so that every real node has a predecessor; then inserting or deleting at the head needs no special case and you simply return dummy.next.

An LRU cache 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 evict-from-back), so get and put are both O(1).