algoadvance

Leetcode 203. Remove Linked List Elements

Problem Statement

Given the head of a linked list and a value val, remove all the nodes of the linked list that have Node.val == val, and return the new head.

Clarifying Questions

  1. What is the structure of the linked list node?
    • The structure is typically defined as: 
      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) {}
};
  2. What should we return if all the nodes in the list are removed?
    • We should return nullptr.
  3. Can the head be nullptr initially?
    • Yes, the head can be nullptr, which represents an empty list.
  4. Are there any constraints on the values of the nodes?
    • The values are integers, but there are no constraints specified in the problem statement regarding their range.

Strategy

  1. Use a dummy node: Create a new dummy node that points to the head of the list. This handles edge cases more smoothly, such as when the head node itself needs to be removed.
  2. Traverse the list: Use two pointers, one (prev) to keep track of the last node that is not removed, and another (curr) to traverse the list.
  3. Check values and update pointers:
    • If curr->val == val, adjust prev->next to skip over the current node.
    • Otherwise, move the prev pointer to the current node.
  4. Return the new list: Return dummy->next, which is the new head of the modified list.

Code

#include <iostream>

// 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) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        
        ListNode* prev = dummy;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            if (curr->val == val) {
                prev->next = curr->next;
            } else {
                prev = curr;
            }
            curr = curr->next;
        }
        
        ListNode* newHead = dummy->next;
        delete dummy;  // Free memory allocated for dummy node
        
        return newHead;
    }
};

// Function to print the list for testing purposes
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

// Main function for simple testing
int main() {
    Solution solution;
    // Create a sample list 1->2->6->3->4->5->6
    ListNode* list = new ListNode(1, new ListNode(2, new ListNode(6, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6)))))));
    
    // Print original list
    std::cout << "Original List: ";
    printList(list);
    
    // Remove all nodes with value 6
    ListNode* modifiedList = solution.removeElements(list, 6);
    
    // Print modified list
    std::cout << "Modified List: ";
    printList(modifiedList);
    
    // Clean up memory
    while (modifiedList != nullptr) {
        ListNode* tmp = modifiedList;
        modifiedList = modifiedList->next;
        delete tmp;
    }

    return 0;
}

Time Complexity

The time complexity is O(n), where n is the number of nodes in the linked list. This is because we traverse each node exactly once. The space complexity is O(1), as we are using only a few extra pointers regardless of the list’s size.

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