The two-pointer technique is a powerful pattern for solving linked list problems efficiently. When you need to find a specific position relative to the end of a linked list without knowing its length, two pointers can help you solve the problem in a single pass.
Unlike arrays, linked lists don't provide direct access to elements by index. To find the 5th element from the end, you'd normally need to:
This requires two passes through the list, which isn't optimal.
The key insight is to maintain two pointers with a fixed gap between them. When the leading pointer reaches the end, the trailing pointer will be exactly where you need it.
For finding the nth node from the end:
A common challenge is handling cases where you need to modify or remove the head node. A "dummy node" technique helps here - create a temporary node that points to the actual head. This way, all operations (including head removal) can be handled uniformly through pointer manipulation.
The dummy node acts as a stable reference point, ensuring your algorithm works consistently whether you're removing the first node, last node, or anything in between.
1def find_nth_from_end(head, n):
2 """Find the nth node from end using two pointers."""
3 first = head
4 second = head
5
6 # Move first pointer n steps ahead
7 for i in range(n):
8 if first is None:
9 return None # n is larger than list length
10 first = first.next
11
12 # Move both pointers until first reaches end
13 while first is not None:
14 first = first.next
15 second = second.next
16
17 return second # This is the nth node from end