algoadvance

Leetcode 203. Remove Linked List Elements

Problem Statement

This is a problem from LeetCode, problem number 203:

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: []

Clarifying Questions

1. What is the range of the input list size?
   • The input list can have from 0 to (10^4) nodes.
2. What is the range of node values?
   • Each node’s value can be any integer.
3. Do we need to consider the cases where the input linked list is null explicitly?
   • Yes, we should handle the case where the input linked list is null.
4. Is this a singly linked list or doubly linked list?
   • This is a singly linked list.

Strategy

1. Dummy Node Approach:
   • Create a dummy node that points to the head of the list. This helps in simplifying edge cases, particularly when the head itself needs to be removed.
2. Iterate Through List:
   • Iterate through the linked list using two pointers: a previous pointer (prev) and a current pointer (curr).
   • Check if the current node’s value equals the target value.
   • If it does, adjust the previous node’s next to skip the current node.
   • If it does not, move the previous pointer to the current node.
   • Always move the current pointer to the next node.
3. Return the new head:
   • Return the next node of the dummy node, which is the new head of the resulting list.

Code

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, curr = head;
        
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }
        
        return dummy.next;
    }
}

Time Complexity

• Time Complexity: (O(n))
  • We traverse each node exactly once.
• Space Complexity: (O(1))
  • We use a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?