algoadvance

You’re 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:

Given the following linked list: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5, return 1 -> 2 -> 5.

Given the following linked list: 1 -> 1 -> 1 -> 2 -> 3, return 2 -> 3.

Clarifying Questions

1. Can the linked list be empty?
   • Yes, it can be. If the list is empty, the output should also be an empty list.
2. Will the linked list always be sorted?
   • Yes, according to the problem statement, the linked list will always be sorted.
3. What should be returned if the linked list contains all duplicates?
   • An empty list should be returned if there are no distinct elements.

Strategy

1. Initialize a dummy node: Create a dummy node to simplify edge cases and use it to build the resulting list.

2. Iterate through the list: Use a pointer (current) to traverse the linked list.

3. Skip duplicates: While traversing, check if the current node has the same value as the next node. If so, skip all nodes with this value.

4. Add non-duplicates to the result list: If the next value is not a duplicate, attach it to the result list.

5. Move to the next unique value: Continue this process until the end of the linked list.

Code

Here is the Python code to solve this problem:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    # Create a dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head
    current = dummy

    while current.next and current.next.next:
        if current.next.val == current.next.next.val:
            # Detected duplicates, get the duplicate value
            dup_val = current.next.val
            # Skip all nodes with this duplicate value
            while current.next and current.next.val == dup_val:
                current.next = current.next.next
        else:
            # No duplicate detected, move to the next node
            current = current.next

    return dummy.next

Time Complexity

• Time Complexity: (O(n)), where (n) is the number of nodes in the linked list. Every node is processed at most once.
• Space Complexity: (O(1)), since we are using a constant amount of extra space (not counting the output list).

This approach efficiently removes all duplicates from the sorted linked list and maintains the required sorted order.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?