Remove Linked List Elements in O(n) Time Complexity using C++

Given the head of a singly 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:

Input: head = [1, 2, 6, 3, 4, 5, 6], val = 6
Output: [1, 2, 3, 4, 5]

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to traverse the linked list and remove nodes that match the given value without disrupting the structure of the list. This problem is significant in various applications such as data cleaning, where unwanted elements need to be removed efficiently.

Potential pitfalls include handling edge cases such as an empty list, all nodes having the target value, or the target value not being present in the list.

Approach

To solve this problem, we can use a single pass through the linked list, which ensures an O(n) time complexity. We will maintain a pointer to the current node and a pointer to the previous node to help with node removal.

Here is a step-by-step approach:

Initialize a dummy node that points to the head of the list. This helps handle edge cases where the head itself needs to be removed.
Use two pointers: one for the current node and one for the previous node.
Traverse the list. If the current node's value matches the target value, adjust the previous node's next pointer to skip the current node.
Otherwise, move the previous pointer to the current node.
Move the current pointer to the next node.
Return the next node of the dummy node as the new head of the list.

Algorithm

Here is a detailed breakdown of the algorithm:

Create a dummy node and set its next pointer to the head of the list.
Initialize two pointers: prev (pointing to the dummy node) and curr (pointing to the head).
While curr is not null:
- If curr's value equals the target value, set prev's next to curr's next.
- Otherwise, move prev to curr.
- Move curr to the next node.
Return dummy's next as the new head of the list.

Code Implementation


#include <iostream>
using namespace std;

// 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) {
        // Create a dummy node that points to the head
        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = dummy;
        ListNode* curr = head;
        
        // Traverse the list
        while (curr != nullptr) {
            if (curr->val == val) {
                // Remove the current node
                prev->next = curr->next;
            } else {
                // Move prev to curr
                prev = curr;
            }
            // Move curr to the next node
            curr = curr->next;
        }
        
        // Return the new head
        ListNode* newHead = dummy->next;
        delete dummy; // Free the dummy node
        return newHead;
    }
};

// Helper function to print the list
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

// Main function to test the solution
int main() {
    // Create a linked list: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(6);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next->next = new ListNode(6);
    
    // Print the original list
    cout << "Original list: ";
    printList(head);
    
    // Remove elements with value 6
    Solution solution;
    head = solution.removeElements(head, 6);
    
    // Print the modified list
    cout << "Modified list: ";
    printList(head);
    
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of nodes in the linked list. This is because we traverse the list once. The space complexity is O(1) as we are using only a few extra pointers and not any additional data structures.

Edge Cases

Consider the following edge cases:

An empty list: The function should return null.
All nodes have the target value: The function should return null.
No nodes have the target value: The function should return the original list.

These cases are handled by the algorithm as it traverses the entire list and adjusts pointers accordingly.

Testing

To test the solution comprehensively, consider the following test cases:

Empty list: []
List with all nodes having the target value: [6, 6, 6]
List with no nodes having the target value: [1, 2, 3]
List with some nodes having the target value: [1, 2, 6, 3, 4, 5, 6]

Use a variety of test cases to ensure the solution handles all scenarios correctly.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Think about edge cases and how to handle them.
Break down the problem into smaller steps and solve each step methodically.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to remove elements from a linked list in O(n) time complexity using C++. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your coding skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: