Introduction
Beyond basic insertion and deletion, linked lists are the foundation of several classic interview and algorithmic problems. These include reversing a list in place, detecting whether a list contains a cycle using Floyd's tortoise and hare algorithm, and finding the middle node in a single pass using two pointers moving at different speeds. Mastering these patterns builds strong intuition for pointer manipulation, which generalizes to many other data structure problems.
Cricket analogy: Classic linked-list problems mirror cricket puzzles: reversing the batting order in place, detecting if a bowler is stuck repeating the same over sequence (a cycle) using a fast and slow scorer walking the card, and finding the middle over of an innings in one pass using two counters moving at different speeds.
Structure/Syntax
class Node:
def __init__(self, value):
self.value = value
self.next = None
def build_list(values):
head = None
tail = None
for v in values:
node = Node(v)
if head is None:
head = tail = node
else:
tail.next = node
tail = node
return headExplanation
Reversing a list in place uses three pointers (prev, current, next_node) and rewires each node's next pointer to point backward, one node at a time. Floyd's cycle detection algorithm uses two pointers, a slow one advancing one node at a time and a fast one advancing two nodes at a time; if they ever meet, a cycle exists, and if the fast pointer reaches None, there is no cycle. Finding the middle node reuses the same two-pointer technique: when the fast pointer reaches the end, the slow pointer is at the middle, because it has moved half as far.
Cricket analogy: Reversing the batting order uses three markers (previous batter, current batter, next batter) flipping each link backward one at a time; Floyd's trick sends a slow scorer and a fast scorer through the over sequence, and if they meet there's a repeating loop; finding the middle over reuses this, since when the fast scorer finishes, the slow one is exactly halfway.
Example
class Node:
def __init__(self, value):
self.value = value
self.next = None
def reverse_list(head):
prev = None
current = head
while current is not None:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev # new head
def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def find_middle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow # middle node (second middle if even length)
# Build 1 -> 2 -> 3 -> 4 -> 5
n5 = Node(5)
n4 = Node(4)
n4.next = n5
n3 = Node(3); n3.next = n4
n2 = Node(2); n2.next = n3
n1 = Node(1); n1.next = n2
print("Has cycle:", has_cycle(n1))
print("Middle value:", find_middle(n1).value)
reversed_head = reverse_list(n1)
values = []
current = reversed_head
while current is not None:
values.append(current.value)
current = current.next
print("Reversed:", values)Complexity
Reversing a list is O(n) time and O(1) extra space since it only rewires existing pointers. Floyd's cycle detection is O(n) time and O(1) space because the fast pointer catches up to the slow pointer within at most n iterations if a cycle exists, avoiding the O(n) extra space that a hash-set-based approach would need. Finding the middle node with the two-pointer technique is also O(n) time and O(1) space, compared to O(n) time and O(1) space for a two-pass approach that first counts length then walks to n/2 — the one-pass two-pointer method is preferred for its single traversal.
Cricket analogy: Reversing the innings order costs O(n) time and O(1) space since only the links are rewired; Floyd's cycle check on the over sequence is also O(n) time and O(1) space, cheaper than a hash-set of past overs; finding the middle over in one pass is O(n) time and O(1) space, preferred over a two-pass count-then-walk approach.
Key Takeaways
- Reversing a linked list in place uses three pointers (prev, current, next_node) and runs in O(n) time, O(1) space.
- Floyd's cycle detection algorithm (tortoise and hare) uses slow and fast pointers; if they meet, a cycle exists.
- Cycle detection with two pointers avoids the O(n) extra memory a hash-set approach would require.
- The two-pointer technique also finds the middle node in one pass: when fast reaches the end, slow is at the middle.
- These pointer-manipulation patterns generalize to many other linked list problems, such as detecting the start of a cycle or checking for palindromes.
Practice what you learned
1. In the in-place reversal algorithm, what does the 'prev' pointer represent at the end of the loop?
2. In Floyd's cycle detection algorithm, how fast does the 'fast' pointer move relative to the 'slow' pointer?
3. What is the space complexity of Floyd's cycle detection algorithm compared to a hash-set-based approach?
4. When the fast pointer reaches the end of the list in the find_middle function, where is the slow pointer?
Was this page helpful?
You May Also Like
Singly Linked Lists
A linear data structure of nodes connected one-way by next pointers, enabling O(1) head insertion.
Doubly Linked Lists
A linked list where each node has both next and previous pointers, allowing efficient bidirectional traversal.
Circular Linked Lists
A linked list variant where the last node points back to the first, forming a continuous loop with no None end.
Common Data Structures Interview Questions
A curated set of frequently asked data structures interview questions with technically accurate, concise answers.