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 Evaluator

Example 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 first 1 node) does not have the value 6, we move pre to point to the 1 node.
Continue to the next node with value 2. The value 2 is not 6 either, so we move pre to this node.
The next node has the value 6, which is the value we want to remove. We change pre.next to skip this 6 node and point to its next node, which is 3. So now pre (which points to 2) has its next pointing to 3. The list now effectively looks like this: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6.
Move to the next nodes with values 3, 4, and 5 in the same manner since their values are not 6.
The next node with value 6 is again the node we want to remove. We change pre.next to skip this node and point to the next, which is null. 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 is null), 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 all 6 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know