Linked List Traversal
Pointers are everything: with careful next-pointer surgery you reverse, merge, and detect cycles in lists using O(1) extra space.
Key ideas
- —A dummy head node removes special cases for the front of the list.
- —Reversing is just relinking next pointers while walking forward once.
- —Fast and slow pointers find the middle and detect cycles in one pass.
Dummy nodes and pointer surgery
Most linked-list bugs live at the boundaries — the head, the tail, an empty list. A dummy node placed before the head gives you a stable handle so insertion and deletion need no special-casing for the first element. Merging two sorted lists is then just splicing nodes onto the dummy in order and returning dummy.next.
Reversal and fast/slow pointers
To reverse a list, walk forward tracking previous, current, and next, flipping each current.next to point back. To find the midpoint or detect a cycle, advance one pointer one step and another two steps; if they meet, there is a cycle, and when the fast pointer reaches the end the slow one sits at the middle.
Practice this
Sources
- Linked listWikipedia
- Cycle detection (Floyd's algorithm)Wikipedia