{x}
blog image

Remove Linked List Elements

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

Solution Explanation for Removing Linked List Elements

This problem involves traversing a singly linked list and removing all nodes with a specific value. The optimal approach uses a dummy node to simplify handling the head of the list.

Approach:

  1. Dummy Node: A dummy node is created and inserted before the head of the original linked list. This simplifies the logic, especially for removing the head node itself. The dummy node's next pointer points to the actual head.

  2. Iteration: The code iterates through the linked list using two pointers:

    • pre: Points to the node before the node being considered.
    • cur: Points to the node currently being evaluated. (In this case, cur is implicitly pre.next)

  3. Conditional Removal: In each iteration:

    • If cur.val (or pre.next.val) is equal to the target val, the node is removed by updating pre.next to skip over the node to be removed (pre.next = pre.next.next).
    • Otherwise, the pointers move to the next node (pre = pre.next).

  4. Return Value: After the iteration, the next pointer of the dummy node points to the new head of the modified linked list, which is then returned.

Time Complexity: O(N), where N is the number of nodes in the linked list. This is because the code iterates through the list once.

Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the list's size. The dummy node and the two pointers do not scale with the input size.

Code Explanation (Python as an example):

# Definition for singly-linked list.
# 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:
        dummy = ListNode(-1, head)  # Create dummy node
        pre = dummy  # Initialize 'pre' pointer to dummy
        while pre.next:  # Iterate until the end
            if pre.next.val != val:  # If value is not target
                pre = pre.next  # Move to next node
            else:
                pre.next = pre.next.next  # Remove the node
        return dummy.next  # Return the new head (after the dummy)

The code in other languages follows the same logic; only the syntax changes. All the provided code snippets implement this efficient approach with a dummy node, resulting in O(N) time and O(1) space complexity.