Remove Duplicates from Sorted Linked List in Java (Time Complexity: O(n))

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 nested loops to compare each node with every other node, but this would result in a time complexity of O(n^2), which is inefficient 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

1. Create a dummy node that points to the head of the list.

2. Use a pointer to traverse the list, checking for duplicates.

3. If duplicates are found, skip all nodes with the duplicate value.

4. Continue until the end of the list is reached.

Code Implementation

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Create a dummy node to handle edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Pointer to traverse the list
        ListNode current = dummy;
        
        while (current.next != null && current.next.next != null) {
            // If the current node's next value equals the next's next value, we have duplicates
            if (current.next.val == current.next.next.val) {
                int duplicateVal = current.next.val;
                // Skip all nodes with the duplicate value
                while (current.next != null && current.next.val == duplicateVal) {
                    current.next = current.next.next;
                }
            } else {
                // Move to the next node
                current = current.next;
            }
        }
        
        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 an empty list.
A list with all duplicate values: The function should return an empty list.
A list with no duplicates: The function should return the original list.

Testing

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

head = [] (empty list)
head = [1,1,1,1] (all duplicates)
head = [1,2,3,4,5] (no duplicates)
head = [1,1,2,3,3,4,5,5] (mixed duplicates)

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Understand the problem constraints and edge cases.
Think about the most efficient way to traverse and manipulate the data structure.
Break down the problem into smaller, manageable steps.

Conclusion

Removing duplicates from a sorted linked list is a common problem that tests your understanding of linked list manipulation and traversal. By using a dummy node and a single-pass approach, we can achieve an efficient solution with a time complexity of O(n).

Additional Resources

For further reading and practice, consider the following resources: