Remove Duplicates from Sorted Linked List - JavaScript Solution with O(n) Time Complexity

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

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

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

Understanding the Problem

The core challenge of this problem is to remove all nodes that have duplicate values from a sorted linked list, ensuring that only distinct values remain. This is significant in scenarios where data integrity and uniqueness are crucial, such as in databases or data processing pipelines.

Common pitfalls include not handling edge cases like an empty list or a list where all elements are duplicates.

Approach

To solve this problem, we can use a two-pointer technique to traverse the linked list and identify duplicates. Here's a step-by-step approach:

Naive Solution

A naive solution would involve using a nested loop to compare each node with every other node, but this would result in a time complexity of O(n^2), which is not efficient for larger lists.

Optimized Solution

An optimized solution involves using a single pass through the list with a dummy node to handle edge cases more gracefully. This approach ensures a time complexity of O(n).

Algorithm

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

Create a dummy node that points to the head of the list.
Initialize a pointer, `prev`, to the dummy node.
Traverse the list with another pointer, `current`.
If `current` and `current.next` have the same value, skip all nodes with this value.
Otherwise, move `prev` to `current`.
Continue until the end of the list.
Return the list starting from `dummy.next`.

Code Implementation

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // Create a dummy node to handle edge cases
    let dummy = new ListNode(0);
    dummy.next = head;
    
    // Initialize pointers
    let prev = dummy;
    let current = head;
    
    while (current !== null) {
        // Check for duplicates
        if (current.next !== null && current.val === current.next.val) {
            // Skip all nodes with the same value
            while (current.next !== null && current.val === current.next.val) {
                current = current.next;
            }
            // Link prev to the node after the last duplicate
            prev.next = current.next;
        } else {
            // Move prev to current
            prev = prev.next;
        }
        // Move current to the next node
        current = current.next;
    }
    
    // Return the modified list
    return dummy.next;
};

Complexity Analysis

The time complexity of this approach is O(n) because we traverse the list only once. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Potential edge cases include:

An empty list: The function should return null.
A list with all duplicate values: The function should return null.
A list with no duplicates: The function should return the original list.

These cases are handled by the dummy node and the traversal logic.

Testing

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

Empty list: head = []
All duplicates: head = [1,1,1]
No duplicates: head = [1,2,3]
Mixed duplicates: head = [1,2,2,3,4,4,5]

Use a testing framework like Jest or Mocha to automate these tests.

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.
Start with a naive solution and then optimize it.
Use diagrams or pseudo-code to visualize the problem.

Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to remove duplicates from a sorted linked list using an optimized approach with O(n) time complexity. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills.

Keep practicing and exploring further to master these concepts.