Linked List Traversal
Algorithm · Starter
Step through it: Fast & Slow Pointers pattern
both start at node 1
Step 1 of 6
Question: does this chain of nodes loop back on itself? Walking it one node at a time never answers that, because inside a loop you just keep going. Instead send two walkers from the start: a slow one moving 1 node per step and a fast one moving 2.
Step 2 of 6
After one step the slow walker is on node 2 and the fast one on node 3.
Step 3 of 6
Again: slow on 3, fast on 5, the last node.
Step 4 of 6
The last node points back to 3, so fast carries on 5 → 3 → 4 while slow steps to 4. They land on the same node.
Step 5 of 6
Why they must meet: inside a loop the fast walker gains one node on the slow one every step, so it catches up. Without a loop, fast would simply fall off the end (null) first. Two walkers at different speeds is called fast and slow pointers.
Step 6 of 6
Your turn.
The task is to traverse the given linked list in straight order.
For example for the following linked list:
The order of traversal should be:
12 → 99 → 37The time complexity is O(n) because we visit every node only once.
Reference
Code
/**
* Traversal callback function.
* @callback traversalCallback
* @param {*} nodeValue
*/
/**
* @param {LinkedList} linkedList
* @param {traversalCallback} callback
*/
export default function traversal(linkedList, callback) {
let currentNode = linkedList.head;
while (currentNode) {
callback(currentNode.value);
currentNode = currentNode.next;
}
}Practice
Fast & Slow Pointers
- Linked List CycleEasy
- Middle of the Linked ListEasy
- Palindrome Linked ListEasy
- Happy NumberEasy
- Linked List Cycle IIMedium
- Find the Duplicate NumberMedium
- Remove Nth Node From End of ListMedium
- Reorder ListMedium
- Sort ListMedium
- Circular Array LoopMedium
- Delete the Middle Node of a Linked ListMedium
- Rotate ListMedium
- Intersection of Two Linked ListsMedium
Spotted a mistake or something unclear? Report it on GitHub.