0083 Remove Duplicates From Sorted List

0083 Remove Duplicates From Sorted List#

Problem#

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Examples#

Example 1:

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

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,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.

Analysis#

  • The key constraint here is we need remove duplicates in-place.

  • Use fast and slow pointer:

    • The fast pointer moves forward, and find a non-duplicated element

    • Then assign the non-duplicate to the slow pointer, and move slow pointer one step forward

    • This makes sure that nums[0:slow] are nonduplicated.

Solution#

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

def build(nums):
    dummy = Node()
    node = dummy
    while nums:
        val = nums.pop(0)
        node.next = Node(val)
        node = node.next 

    return dummy.next 
def LinkedListToList(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res    

def removeDuplicates(head):
    if not head:
        return head

    slow, fast = head, head
    while fast:
        if slow.val != fast.val:
            # move slow forward and swap with fast so that no duplicates before slow
            slow.next = fast
            slow = slow.next

        fast = fast.next
    return head

# test
nums = [1,1,2]
head = build(nums)
head = removeDuplicates(head)
print(LinkedListToList(head))

nums = [0,0,1,1,1,2,2,3,3,4]
head = build(nums)
head = removeDuplicates(head)
print(LinkedListToList(head))

[1, 2]
[0, 1, 2, 3, 4]
Contents