Remove Duplicates from Sorted List II

January 14, 2024

Problem #

Given the head of a sorted linked list, delete all nodes that have duplicate numbers (leaving only distinct numbers from the original list) and return the sorted list.

Example:

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

Solution Approach #

The solution involves using two pointers, one to iterate through the list (current) and another to ensure the connection between non-duplicate nodes (prev).

Algorithm Steps #

1. Create a dummy node with next pointing to the head and a prev pointer pointing to it.
2. Iterate through the list with the current pointer.
3. If duplicates are found, skip them and update the next of prev.
4. If no duplicate, move prev to current.
5. Continue till the end of the list.
6. Return the next of the dummy node, which is the head of the modified list.

Code (Python) #

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

def deleteDuplicates(head):
    dummy = ListNode(0, head)
    prev = dummy

    while head:
        if head.next and head.val == head.next.val:
            while head.next and head.val == head.next.val:
                head = head.next
            prev.next = head.next
        else:
            prev = prev.next
        head = head.next

    return dummy.next

# Test the function
# Example linked list creation and test
head = ListNode(1, ListNode(2, ListNode(3, ListNode(3, ListNode(4, ListNode(4, ListNode(5)))))))
print(deleteDuplicates(head))  # Output: [1, 2, 5]

Time Complexity #

O(n), where n is the number of nodes in the linked list. The list is traversed once.

Space Complexity #

O(1), as no extra space is used apart from the pointers.