061.md

203. Remove Linked List Elements

Difficulty: 🟢 Easy

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.

Examples:

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

Solutions

O(n) solution

Python 3

# 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: Optional[ListNode], val: int) -> Optional[ListNode]:
        new_head = ListNode()
        new_head.next = head
        
        prev, curr = new_head, new_head.next
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next
        return new_head.next

The given solution provides an iterative approach to remove all nodes with the value val from the linked list.

Here is a step-by-step overview of the solution:

1. Create a new head node and set its next pointer to the original head of the linked list. This step allows handling the case where the head itself needs to be removed.
2. Initialize two pointers: prev to keep track of the previous node and curr to iterate through the list starting from the head.
3. Traverse the linked list using the curr pointer:
   • If the value of the current node (curr.val) is equal to val, update the next pointer of the previous node (prev.next) to skip the current node.
   • Otherwise, update both prev and curr to move forward in the list.
4. Return the next pointer of the new head, which will be the head of the modified list.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the linked list. We traverse the list once, visiting each node at most once.

The space complexity is O(1) because we are using a constant amount of additional space to store the pointers.

Summary

The given solution provides an iterative approach to remove all nodes with a specific value from a linked list. It maintains two pointers to keep track of the previous node and the current node. The solution runs in linear time and constant space complexity.

NB: If you want to get community points please suggest solutions in other languages as merge requests.