Remove Linked List Elements
Delete every node with the given value — dummy head + walking predecessor.
2 min read
linked-list
Problem#
Remove all nodes whose val == target from a singly linked list.
Examples#
[1,2,6,3,4,5,6], val = 6→[1,2,3,4,5][7,7,7,7], val = 7→[]
Constraints#
0 <= n <= 10^4.
Approach#
Dummy head + predecessor pointer. If pre->next matches, splice it out without advancing pre. Otherwise advance.
Solution#
class Solution {public: ListNode* removeElements(ListNode* head, int val) { ListNode dummy(0, head); ListNode* pre = &dummy; while (pre->next) { if (pre->next->val == val) { ListNode* del = pre->next; pre->next = del->next; delete del; } else { pre = pre->next; } } return dummy.next; }};func removeElements(head *ListNode, val int) *ListNode { dummy := &ListNode{Next: head} pre := dummy for pre.Next != nil { if pre.Next.Val == val { pre.Next = pre.Next.Next } else { pre = pre.Next } } return dummy.Next}from typing import Optional
class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy = ListNode(0, head) pre = dummy while pre.next: if pre.next.val == val: pre.next = pre.next.next else: pre = pre.next return dummy.nextfunction removeElements(head, val) { const dummy = new ListNode(0, head); let pre = dummy; while (pre.next) { if (pre.next.val === val) { pre.next = pre.next.next; } else { pre = pre.next; } } return dummy.next;}class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0, head); ListNode pre = dummy; while (pre.next != null) { if (pre.next.val == val) { pre.next = pre.next.next; } else { pre = pre.next; } } return dummy.next; }}function removeElements(head: ListNode | null, val: number): ListNode | null { const dummy = new ListNode(0, head); let pre: ListNode = dummy; while (pre.next) { if (pre.next.val === val) { pre.next = pre.next.next; } else { pre = pre.next; } } return dummy.next;}Editorial#
Not advancing pre after a splice is the subtle bit — the new pre->next may also be a match. The dummy handles consecutive-match-at-head uniformly.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#