DSA · Chapter 14 of 40
Linked List Problems
Three techniques solve most linked-list questions: reversing pointers iteratively, using fast and slow pointers, and using a dummy head node to simplify edge cases.
Fast and slow pointers detect cycles (Floyd's algorithm) and find the middle node in one pass.
Reversal
Keep prev, cur and next. Point cur.next at prev, then advance all three. When cur becomes None, prev is the new head.
Cycle detection
Move slow one step and fast two steps. If they ever meet, the list has a cycle; if fast reaches the end, it does not.
Example 1 (python)
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prevIterative reversal uses O(1) extra space.
Example 2 (python)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseFloyd's tortoise and hare detects a loop in O(n) time, O(1) space.
Key points
- Iterative reversal uses prev, cur and next pointers.
- Fast/slow pointers find the middle and detect cycles.
- A dummy head removes special cases for empty lists.
- Always check for None before dereferencing .next.
💡 Note: Mention the O(1) space advantage of the iterative approach over recursion.