LeetCode Link: 203. Remove Linked List Elements

Problem Definition

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 104].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

Thought Process

Let's take the linked list 1 → 4 → 2 → 4 as an example and remove the element 4.

In this scenario, the removal operation involves making the next pointer of the current node point directly to the node after the next one.

However, due to the nature of a singly linked list, each node can only point to the next node. In the example above, the second and fourth nodes (both containing the value 4) were removed. But what if the node to be deleted is the head node?

This brings us to two approaches for handling such operations:

  1. Directly removing nodes from the original linked list.
  2. Using a dummy head node to assist with the removal operation.

Let's first explore the direct removal from the original linked list:
In this method, we perform the removal directly on the original linked list without any additional setup.

The operation for removing the head node differs from removing other nodes. This is because other nodes in the linked list are removed by adjusting the next pointer of their preceding node, but the head node has no preceding node.

So, how do we remove the head node? The solution is quite simple: just shift the head node one step forward, making the second node the new head. In this way, the original head node is effectively removed from the linked list.

Removing the head node differs from removing other nodes, as you've noticed. When writing code, you'll find that you need a separate logic block specifically to handle the removal of the head node.

So, is there a way to unify the logic for removing nodes from a linked list?

Yes, you can introduce a dummy head node. With a dummy head node, all nodes in the original linked list—including the original head—can be removed using the same logic.

Let's see how to set up a dummy head and apply it to the same linked list, where we aim to remove the element 1.

Steps to Remove Element 1:

  1. Start with the dummy node and iterate through the list.
  2. When the target node (with value 1) is found, adjust the previous node's next pointer to skip this node.
  3. Delete the node from memory (if necessary, depending on the language or system).
  4. At the end, return the new head by returning dummyNode->next. This points to the actual start of the modified list.

Solution 1

Directly use the original linked list to perform the node removal operation.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # Remove head nodes with the given value
        while head is not None and head.val == val:
            tmp = head
            head = head.next

        # Remove non-head nodes with the given value
        cur = head
        while cur is not None and cur.next is not None:
            if cur.next.val == val:
                tmp = cur.next
                cur.next = cur.next.next
            else:
                cur = cur.next

        return head

Time Complexity: O(n)

Space Complexity: O(1)

Solution 2

Set up a virtual head node when performing the remove node operation.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Create dummy head
        dummy_head = ListNode(next = head)
        
        # traverse the list to delete target
        current = dummy_head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy_head.next

Time Complexity: O(n)

Space Complexity: O(1)

Solution 3

This problem can also be solved using a recursive approach:

  • Base case: For an empty linked list, no elements need to be removed.
  • Recursive case: First, check if the value of the head node is equal to val. If it is, remove the head node; the answer will be the result of recursively processing the subsequent nodes after the head. If the value of the head node is not equal to val, then the answer will be a concatenation of the head node and the new linked list obtained by recursively processing its subsequent nodes.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # Base case: if the list is empty, return None
        if head is None:
            return None

        # Recursive case
        if head.val == val:
            new_head = self.removeElements(head.next, val)
            del head  # Optional: explicitly delete the node
            return new_head
        else:
            head.next = self.removeElements(head.next, val)
            return head

Time Complexity: O(n)

Space Complexity: O(n)