Algocademy Logo

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


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 using extra space. This is a common problem in linked list manipulation, often encountered in various applications such as memory management, data filtering, and more.

Potential pitfalls include handling the removal of nodes at the beginning of the list and ensuring that the list remains properly linked after node removal.

Approach

To solve this problem, we can use a single pass through the linked list, maintaining a reference to the previous node to help with node removal. Here’s a step-by-step approach:

Naive Solution

A naive solution would involve creating a new linked list and copying over only the nodes that do not match the given value. However, this approach uses extra space and is not optimal.

Optimized Solution

We can optimize the solution by modifying the linked list in place. The idea is to use two pointers: one to traverse the list and another to keep track of the last node that does not need to be removed. This way, we can adjust the pointers to skip over nodes that need to be removed.

Algorithm

Here’s a step-by-step breakdown of the optimized algorithm:

  1. Create a dummy node that points to the head of the list. This helps handle edge cases where the head needs to be removed.
  2. Initialize two pointers: one for the current node and one for the previous node.
  3. Traverse the list. For each node:
    • If the node’s value matches the given value, adjust the previous node’s next pointer to skip the current node.
    • Otherwise, move the previous pointer to the current node.
  4. Return the next pointer of the dummy node, which points to the new head of the list.

Code Implementation

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

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Create a dummy node that points to the head
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Initialize current and previous pointers
        ListNode current = head;
        ListNode prev = dummy;
        
        // Traverse the list
        while (current != null) {
            if (current.val == val) {
                // Skip the current node
                prev.next = current.next;
            } else {
                // Move the previous pointer
                prev = current;
            }
            // Move the current pointer
            current = current.next;
        }
        
        // Return the new head
        return dummy.next;
    }
}

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) since we are not using any extra space other than a few pointers.

Edge Cases

Potential edge cases include:

Each of these cases is handled by the algorithm as it uses a dummy node and adjusts pointers accordingly.

Testing

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

Use a testing framework like JUnit to automate these tests.

Thinking and Problem-Solving Tips

When approaching linked list problems, always consider edge cases and think about how to handle node removal and pointer adjustments. Practice by solving similar problems and studying different algorithms for linked list manipulation.

Conclusion

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

Additional Resources