203. Remove Linked List Elements
Problem Description
The problem requires us to modify a linked list by removing all nodes that contain a specified value. Given the head of a linked list and an integer val
, we must iterate through the linked list and delete any node where the Node.val
is equal to val
. The function should then return the head of the modified linked list, which might be different from the initial head if the head node itself needed to be removed.
Intuition
To solve this problem, we need to iterate through the linked list and keep track of the previous node (pre
) so we can modify its next
pointer when we find a node that needs to be removed. The challenge is that the nodes to be removed can be anywhere in the list, including the head. To handle the case where the head itself needs to be removed, we introduce a dummy node with an arbitrary value that points to the head of the linked list. This dummy node acts as a placeholder that makes it easier to handle edge cases, particularly when we need to remove the head node.
Our approach involves iterating over the linked list with a pointer pre
initialized to the dummy node. For each node, we check if the next
node has a value equal to val
. If it does not, we move pre
to the next node. If it does, instead of moving to the next node, we change the next
pointer of pre
to skip over the node with the val
we want to remove, effectively removing it from the linked list. We continue this process until we have checked all nodes. Finally, we return the next
node of the dummy, which represents the new head of the modified linked list.
Learn more about Recursion and Linked List patterns.
Solution Approach
The implementation begins with creating a dummy node. This dummy node is a commonly used pattern when dealing with linked list modifications, as it simplifies edge case handling when the head of the list might be removed. We can say that the dummy node acts as a fake head (or a sentinel) to the list. The dummy node is linked to the actual head of the list.
After initializing the dummy node, we introduce a pointer pre
that is used to traverse the list. This pointer starts at the dummy node.
The core of the solution is a while
loop that continues until pre.next
is None
(meaning we have reached the end of the list). Inside the loop, the condition if pre.next.val != val
is checked. If this condition is true, it means the current pre.next
node does not need to be removed, and we can safely move pre
to point to this node (pre = pre.next
). If the condition is false, we have encountered a node with the value val
, which must be removed. To remove this node, we alter pre.next
to skip over the current pre.next
node and point to pre.next.next
. This effectively removes the unwanted node from the list.
After the loop terminates, we return dummy.next
, which is the new head of the modified list. This works even if the original head was removed because dummy.next
will now point to the first node with a value different from val
.
The aforementioned approach leverages basic linked list traversal and node skipping techniques. The dummy node pattern helps to avoid special case handling for the head of the list. This pattern is also known for its utility in simplifying the code and making the algorithm cleaner and easy to understand.
The overall time complexity of the solution is O(n)
, where n
is the number of nodes in the list, since we may have to traverse the entire list in the worst case. The space complexity is O(1)
as we only use a fixed amount of extra space.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have a linked list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
and we want to remove all nodes with the value 6
.
Here's a step-by-step illustration:
-
Create a dummy node with an arbitrary value (can be anything as it will not be used) and point its
next
to the head of the list. So, now we have dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6. -
Initialize a pointer
pre
to point at the dummy node. So,pre
is now pointing to dummy. -
Begin iterating over the list. Since
pre.next
(the first1
node) does not have the value6
, we movepre
to point to the1
node. -
Continue to the next node with value
2
. The value2
is not6
either, so we movepre
to this node. -
The next node has the value
6
, which is the value we want to remove. We changepre.next
to skip this6
node and point to its next node, which is3
. So nowpre
(which points to2
) has itsnext
pointing to3
. The list now effectively looks like this: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. -
Move to the next nodes with values
3
,4
, and5
in the same manner since their values are not6
. -
The next node with value
6
is again the node we want to remove. We changepre.next
to skip this node and point to the next, which isnull
. The modified list now looks like this: dummy -> 1 -> 2 -> 3 -> 4 -> 5 ->null
. -
Since we've reached the end of the list (
pre.next
isnull
), we stop iterating. -
Finally, we return the node right after our dummy, which is the new head of the modified list. The returned list is
1 -> 2 -> 3 -> 4 -> 5
, as all6
nodes have been removed.
Therefore, by using a dummy node and the pointer pre
, we managed to remove all the nodes with the value 6
without having to deal with special cases like the head of the list being removed. This demonstrates the elegance and effectiveness of the solution approach.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next=None):
4 self.val = val
5 self.next = next
6
7class Solution:
8 def removeElements(self, head: ListNode, val: int) -> ListNode:
9 # Create a dummy node that acts as the new head of the list with a sentinel value
10 dummy_node = ListNode(-1)
11 dummy_node.next = head
12
13 # Initialize a pointer to track the current node we're examining
14 current_node = dummy_node
15
16 # Iterate over the list
17 while current_node.next is not None:
18 # If the value of the next node is the one we want to remove
19 if current_node.next.val == val:
20 # Remove it by skipping the node
21 current_node.next = current_node.next.next
22 else:
23 # Move to the next node otherwise
24 current_node = current_node.next
25
26 # Return the modified list, starting from the node after the dummy node
27 return dummy_node.next
28
1/**
2 * Definition for singly-linked list.
3 */
4public class ListNode {
5 int val;
6 ListNode next;
7
8 ListNode() {}
9
10 ListNode(int val) {
11 this.val = val;
12 }
13
14 ListNode(int val, ListNode next) {
15 this.val = val;
16 this.next = next;
17 }
18}
19
20class Solution {
21 public ListNode removeElements(ListNode head, int val) {
22 // Create a dummy head to simplify edge cases such as removing the first element
23 ListNode dummyHead = new ListNode(-1);
24 dummyHead.next = head;
25
26 // Initialize the previous node as the dummy node
27 ListNode previousNode = dummyHead;
28
29 // Iterate through the list
30 while (previousNode.next != null) {
31 // Check if the current node has the value we need to remove
32 if (previousNode.next.val == val) {
33 // Remove the current node from the list
34 previousNode.next = previousNode.next.next;
35 } else {
36 // Move to the next node
37 previousNode = previousNode.next;
38 }
39 }
40
41 // Return the new head of the list, which is the next of dummy node
42 return dummyHead.next;
43 }
44}
45
1class Solution {
2public:
3 // Function to remove all nodes with a specific value from a linked list.
4 ListNode* removeElements(ListNode* head, int val) {
5 // Create a dummy node that serves the purpose of an anchor for the new list without the given value.
6 ListNode* dummyNode = new ListNode();
7 dummyNode->next = head;
8
9 // Initialize a pointer that will traverse the list, starting from the dummy node.
10 ListNode* current = dummyNode;
11
12 // Iterate through the list until the end is reached.
13 while (current->next) {
14 // Check if the next node's value matches the value to be removed.
15 if (current->next->val == val) {
16 // If a match is found, skip over the node with the matching value.
17 current->next = current->next->next;
18 } else {
19 // Otherwise, move to the next node.
20 current = current->next;
21 }
22 }
23
24 // Return the next node of dummy as it is the new head of the modified list.
25 return dummyNode->next;
26 }
27};
28
1// Function to remove elements from a linked list that have a specific value.
2// head: The first node of the linked list.
3// val: The value to remove from the linked list.
4// Returns the new head of the linked list after removals.
5function removeElements(head: ListNode | null, val: number): ListNode | null {
6 // Initialise a dummy node with the next pointer pointing to the head of the list.
7 // This simplifies edge cases such as trying to delete the head of the list.
8 const dummy: ListNode = new ListNode(0, head);
9
10 // This points to the current node we're examining, starting from the dummy.
11 let current: ListNode = dummy;
12
13 // Iterate through the list as long as the next node exists.
14 while (current.next !== null) {
15 // If the value of the next node is the target value, bypass the next node.
16 if (current.next.val === val) {
17 current.next = current.next.next; // Skip the node to remove it.
18 } else {
19 current = current.next; // Move to the next node if it's not to be removed.
20 }
21 }
22
23 // Return the next node of the dummy, which represents the new head after removals.
24 return dummy.next;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(n)
, where n
is the number of elements in the linked list. The while loop iterates through each node in the linked list a single time, checking if the node's value matches the target value val
and removing it if necessary.
Space Complexity
The space complexity of the provided code is O(1)
. This is because the code only uses a constant amount of extra space: one dummy node (dummy
) and one pointer (pre
). The removal of elements is done in-place, not requiring any additional data structures that would scale with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!