203. Remove Linked List Elements

Description

Given the head of a singly linked list and an integer val, the task is to remove all the nodes of the linked list that have val as their value and return the new head of the list.

Intuition

When removing elements from a linked list, especially when the nodes to be removed include the head, it's important to carefully adjust the pointers. The key is to iterate through the list while maintaining the integrity of the connections between nodes that do not need to be removed.

Approach

1. Handle Removal of Head Nodes: - Begin by checking if the head node itself contains the target value val. If it does, move the head pointer to the next node, effectively removing the current head. Repeat this process until the head no longer contains val or the list becomes empty.
2. Iterate Through the List: - Once the head is correctly positioned, iterate through the list using a pointer (curr). - For each node, check if the next node contains the value val. - If it does, adjust the next pointer of the current node to skip over the node with val, effectively removing it from the list. - If it does not, simply move the pointer to the next node.
3. Return the New Head: - After processing all nodes, return the new head of the list.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the linked list. Each node is visited exactly once.

Space Complexity:

O(1). The algorithm operates in-place, using only a constant amount of extra space.

Code

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head && head->val == val) {
            head = head->next;
        }

        ListNode* curr = head;
        while (curr && curr->next) {
            if (curr->next->val == val) {
                curr->next = curr->next->next;
            } else {
                curr = curr->next;
            }
        }

        return head;
    }
};

Python

# 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:
        while head and head.val == val:
            head = head.next

        curr = head
        while curr and curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next
            else:
                curr = curr.next

        return head

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }

        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }

        return head;
    }
}

JavaScript

var removeElements = function(head, val) {

    while(head && head.val === val){
        head = head.next
    }

   let curr = head
   while(curr && curr.next){

    if(curr.next.val === val){
        curr.next = curr.next.next
        
    }else{
        curr = curr.next
    }
   }
   return head
};