Return the k-th node from the end of a singly linked list in one pass
Given the head of a singly linked list, return the node that is k positions from the end (k = 0 is the last node). Return nil if k is out of range.
Constraints:
- The list is singly linked — you cannot walk backwards.
- Aim for one pass: O(n) time, O(1) extra space.
type Item struct {
val int
next *Item
}
func kthFromEnd(k int, head *Item) *Item {
// your code here
}Write the implementation.
Use two pointers with a gap of k. Advance a lead pointer k steps ahead first; if it runs off the list before that, k is out of range — return nil. Then move lead and a trail pointer (starting at head) together until lead reaches the last node. trail is now k from the end. One pass, O(n) time, O(1) space — no length precount and no second traversal.
- ✗Precounting length and traversing twice instead of one two-pointer pass
- ✗Forgetting to return
nilwhenkexceeds the list length - ✗Claiming a stack or recursion gives O(1) space when it is O(n)
- →How do you detect that
kis out of range during the lead pointer's head start? - →Why is the gap-of-k invariant preserved as both pointers advance together?
Solution
func kthFromEnd(k int, head *Item) *Item {
lead := head
// Head start of k steps; if the list is shorter, k is out of range.
for i := 0; i < k; i++ {
if lead == nil {
return nil
}
lead = lead.next
}
if lead == nil {
return nil
}
trail := head
// Move both until lead sits on the last node.
for lead.next != nil {
lead = lead.next
trail = trail.next
}
return trail
}How it works. A gap of k nodes is kept between lead and trail. When lead reaches the last node, trail lags by exactly k — which is the k-th from the end.
Complexity. One pass: O(n) time, O(1) space. No need to precount the length or traverse the list a second time.
Edge cases. k = 0 returns the last node; k ≥ length returns nil.
