Problem overview
The function remove receives the head of a singly linked list and a value val. It must delete every node whose val field equals val and return the head of the remaining list. In Rust the list is an Option<Box<ListNode>>, with None as the empty list.
With [1, 2, 6, 3, 4, 5, 6] and val = 6 the result is [1, 2, 3, 4, 5]. The statement asks for O(n) time and O(1) extra space, so the list is edited in place with a single walk.
Approach: stand one node before the one you test
To delete a node from a singly linked list you change the next of the node before it. So the walker must stand on the predecessor and look one step ahead: if node.next holds the value, skip it; otherwise move forward.
That raises a problem for the head. The first node has no predecessor, so removing it would be a special case, and so would a list whose first several nodes all match. A dummy node removes the special case. Put a throwaway node with value 0 in front of the list, walk from it, and at the end return dummy.next. Now every real node has a predecessor.
The one subtle rule: after removing a node, do not advance. The node that took its place may match too. With [6, 6], advancing after the first removal would step over the second 6.
Here is the walk on [1, 6, 6, 2] with val = 6. The list is dummy -> 1 -> 6 -> 6 -> 2 and the walker starts on the dummy:
- The next node is 1, which does not match, so the walker moves onto the node 1.
- The next node is the first 6, which matches. It is spliced out, giving
1 -> 6 -> 2, and the walker stays on 1. - The next node is now the second 6, which matches too. It is spliced out, giving
1 -> 2. - The next node is 2, so the walker moves onto it. Its
nextisNone, the loop ends, and the function returns the list after the dummy:[1, 2].
Step by step
- Create
dummy.Box::new(ListNode::new(0))is a boxed node with value 0, stored in amutvariable because itsnextwill change. - Attach the list.
dummy.next = headmoves the whole list into the dummy. - Create the walker.
let mut node = &mut dummyis a mutable reference to the dummy. The reference variable ismutso it can later be pointed at other nodes. - Loop while there is a next node:
while node.next.is_some(). - Test the next node's value.
node.next.as_ref().unwrap().val == val.as_ref()borrows the content of the option instead of moving it, andunwrap()is safe because the loop condition just checkedis_some(). - On a match, splice the node out.
take()the removed node's ownnextintoremoved_next, then assign that tonode.next. The old box loses its owner and is freed. Leavenodewhere it is. - Otherwise, advance:
node = node.next.as_mut().unwrap()turns the walker into a mutable reference to the next box. - Return
dummy.nextas the last expression.
The solution in Rust
impl Solution {
fn remove(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(0));
dummy.next = head;
let mut node = &mut dummy;
while node.next.is_some() {
if node.next.as_ref().unwrap().val == val {
let removed_next = node.next.as_mut().unwrap().next.take();
node.next = removed_next;
} else {
node = node.next.as_mut().unwrap();
}
}
dummy.next
}
}
Rust details worth knowing:
- Why
take()is needed. The walker is only a&mutreference, and you cannot move a field out of something you merely borrow.take()moves the value out and leavesNonein its place, so the borrowed node stays valid. Writingnode.next = node.next.as_mut().unwrap().next;fails with error E0507, "cannot move out of a mutable reference". - Assigning drops.
node.next = removed_nextreplaces the old value ofnode.next, the matching node, whose ownnextis alreadyNone. The old box is dropped and freed immediately. as_ref()versusas_mut(). Reading the value needs only a shared borrow, so the test usesas_ref(). Changing the node's link or moving the walker usesas_mut().- The reference outlives its use. After the loop the last use of
nodeis behind us, sodummy.nextcan be moved out even thoughnodeborroweddummyearlier.
Why the walker is a reference
The walker is a &mut Box<ListNode>: it borrows a node that the list still owns. That is why the loop never copies or moves nodes while it searches. The only moves are the two in the splice, and both go through take() or an assignment to node.next, which are the places where ownership really changes hands. Keeping this split in mind makes most linked-list code in Rust easier to write: walk with references, and change ownership only where a link is cut or joined.
Complexity
Time: O(n). Each pass of the loop either removes one node or moves the walker forward one node, so there are at most n passes, each doing constant work.
Space: O(1). The dummy node and the walker are the only additions. Removed nodes are freed, not stored.
Edge cases and common mistakes
- Removing the head.
[6, 1]withval = 6gives[1]. The dummy makes this the same operation as any other removal. - Consecutive matches.
[1, 6, 6, 2]gives[1, 2]. This works only because the walker stays put after a removal. - Everything matches.
[7, 7, 7, 7]withval = 7gives[], sincedummy.nextends asNone. - Empty list.
Nonenever enters the loop, and the function returnsNone. - Returning
head. The originalheadwas moved into the dummy, and if the first node was removed it no longer exists. Returndummy.next. - Advancing after every pass. This skips the node that slid into place after a removal.
Testing
[1, 2, 6, 3, 4, 5, 6]withval = 6gives[1, 2, 3, 4, 5].[7, 7, 7, 7]withval = 7gives[].[1, 6, 6, 2]withval = 6gives[1, 2].[]with any value gives[].
