A linked list stores each element in a node that points to the next node. Inserting or deleting at a known position is O(1) (just rewire pointers), but reaching the k-th element is O(n) because there is no index — you have to follow the chain.
Walk it with pointers
Every linked-list problem is solved by carefully moving one or more pointers. Two patterns cover most cases: reverse (three pointers) and fast/slow (one moves twice as fast).
Reverse a singly linked list
prev = null; curr = head
while curr != null:
nxt = curr.next // save the rest
curr.next = prev // flip the link
prev = curr // advance
curr = nxt
return prev // new headO(n)→O(1)
One pass; only a few pointers of extra memory.
⚡ The edge
- Three pointers reverse a list: prev, curr and next — save the next node before you flip the current link, or you lose the rest of the list.
- Fast/slow pointers find the middle (slow is at the midpoint when fast reaches the end) and detect a cycle (they meet if one exists).
Worked example
Reverse the list 1 -> 2 -> 3. What is the new order?
- Start with prev = null, curr = 1. Save next, point 1 back to null, move on: prev = 1.
- Repeat: 2 now points to 1 (prev = 2), then 3 points to 2 (prev = 3).
- When curr falls off the end, prev (3) is the new head: 3 -> 2 -> 1.
Answer: 3 -> 2 -> 1, in O(n) time and O(1) space
Worked example
How do you detect a cycle in a linked list without extra memory?
- Use two pointers: slow moves one node at a time, fast moves two.
- If the list ends (fast hits null), there is no cycle.
- If there is a cycle, fast eventually laps and meets slow inside the loop.
Answer: Floyd's fast/slow pointers — O(n) time, O(1) space
⚠ Watch out
- Always save next before rewiring a pointer, or you lose access to the rest of the list.
- Guard against null: check node and node.next before following them.
- There is no O(1) random access — reaching position k costs O(k).