Remove the node k positions from the end of a singly linked list, counting the tail as position zero. For 10 -> 20 -> 30 -> 40, k = 0 removes 40, k = 1 removes 30, and k = 3 removes 10. If k is at least the list length, return the original list unchanged. Inputs use nonnegative k.
Find the predecessor without knowing the length
A two-pass solution first counts the nodes and then walks to the target's predecessor. That is O(n) time and constant auxiliary space, and is a useful baseline. Two pointers let us find the same predecessor during one forward traversal after an initial offset.
Start lead and follow at the head. Advance lead k + 1 links, returning the original head if lead becomes null before completing those advances. The extra one positions follow at the predecessor of the node to delete once lead reaches the tail. The gap is measured in links, so draw actual nodes before deciding whether an offset of k or k + 1 matches the later stopping condition.
Distinguish head removal from an invalid offset
If lead becomes null exactly after the k + 1 advances, the target is the head. Return head.next. For a four-node list and k = 3, those four advances end exactly at null, so removing the head is valid. For k = 4, the algorithm discovers null before completing the fifth advance, so it returns the list unchanged.
For k = 1, lead first advances two links, from 10 to 30. Move both pointers until lead is the tail. They then point to 20 and 40. The target is follow's next node, 30. Assign follow's next link to the node after 30, reconnecting 20 directly to 40.
Prove that the gap identifies the target
After initialization, lead is k + 1 links ahead of follow. Moving both one link preserves that distance. When lead is at the final node, there are exactly k nodes after follow's next node. Therefore follow's next node is the one whose zero-based distance from the end is k.
The head-removal case needs a separate return because no ordinary predecessor exists before the head. A dummy node is an alternative design that supplies such a predecessor. Whichever form you choose, the caller must assign the returned head. Ignoring it makes a correct head deletion appear to have failed.
Mutation and ownership
The reference-based versions relink the existing chain. They do not shift data values between nodes. That preserves the meaning of the remaining node identities, although an external reference to the removed node can still exist. Ownership-based implementations must detach and move the relevant links without leaving multiple mutable owners.
The scan takes O(n) time. The usual pointer version uses O(1) auxiliary space. Read the language implementation's allocation choices before extending that claim: a version that materializes all values or clones a suffix has a different storage cost. The input is assumed acyclic so forward traversal eventually reaches null.
Tests and adaptations
Test every valid k for a small list, k equal to its length, and a much larger k. Include an empty list, removing the only node of a singleton, removing a tail, and removing the head. Repeated values prevent a test from accidentally identifying the target by value instead of position.
For an independent oracle, convert the original list to an array and remove index length - 1 - k only when that index is valid. Compare the resulting sequence and check that no cycle was introduced. If a caller instead numbers positions from one, translate that input once at the boundary. Mixing the two conventions inside the pointer loop usually produces an off-by-one deletion.
Rust implementation
The code first counts the follower steps through an immutable borrow, then takes a mutable walk. This avoids simultaneous aliasing mutable pointers.
The course supplies any declared node types and invokes the entry in impl Solution, or the design constructor shown here. Owned values move unless borrowed or cloned; the signature makes that choice explicit. An Option separates a missing node or result from a valid value. The runner enables integer overflow checks, so wider constraints require deliberate type and arithmetic changes.
impl Solution {
pub fn mirror_delete(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
/*
We use 2 pointers (lead and follow) that start at the head.
Rust allows only one reference into the list while we change it,
so the lead pointer makes its trip first and counts the steps
the follow pointer will then take.
*/
let mut lead = head.as_deref();
/*
Since we want to delete the k node,
we set our follow pointer to be one spot beyond the deleted node.
So instead of iterating `0 to i < k` as with most problems,
we iterate `0 to i < k + 1` to account for that extra spot.
*/
for _ in 0..k + 1 {
match lead {
// If we hit the end, k is larger than our linked list,
// so we return the head without deleting an item.
None => return head,
Some(node) => lead = node.next.as_deref(),
}
}
/*
Our lead pointer will end exactly at the end of the list (None)
when the head node should be removed (k == linked list length - 1).
Since we iterate to k + 1, our lead pointer is 1 item past
the end of the linked list.
*/
let Some(mut lead) = lead else {
return head.and_then(|node| node.next);
};
// Increment until lead reaches the tail.
// Once here, we know the node we want to delete is at k, and our follow is at k + 1.
let mut follow_steps = 0;
while let Some(next) = lead.next.as_deref() {
lead = next;
follow_steps += 1;
}
// Now the follow pointer takes the same steps from the head
let mut head = head;
let mut follow = head.as_deref_mut()?;
for _ in 0..follow_steps {
follow = follow.next.as_deref_mut()?;
}
// Delete the kth node (skip past it in our linked list)
let deleted = follow.next.take();
follow.next = deleted.and_then(|node| node.next);
// The head will be the same, but the list will not contain the node we deleted
head
}
}
Practice this implementation
Open Mirror Delete to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.
For more Rust conventions and practice problems, use the Rust interview guide.