82. Remove Duplicates from Sorted List II

LeetCode 82. Remove Duplicates from Sorted List II

Description

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.

Tags

Linked List

Solution

A dummy head is created and connects to head. Assign 3 pointers onto the linked list: pre (which starts from the dummy head), cur (which starts from head) and next (which is only initialized when used). Traverse the linked list with cur. The loop condition is cur != nil && cur.Next != nil. There are 2 scenarios in the loop. If cur's next value is NOT equal to that of cur, it means that the node cur pointing to needs to be preserved. Thus, just move forward and assign pre to the cur's old position. Otherwise, we find a string of duplicated nodes and cur is pointing to the head of it. We use next to find the next node whose value is not same as cur's. When we find, we assign pre.Next to next, and move cur to pre because cur will move one step forward after every single loop. At last, we return the next node of dummy head.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

// code here.
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
		    return head
	  }
    dummyHead := &ListNode{-114514, head}
    pre := dummyHead
    for cur := head; cur != nil && cur.Next != nil; cur = cur.Next {
        if cur.Val != cur.Next.Val {
            pre = cur
            continue
        }
        next := cur.Next
        for next != nil && cur.Val == next.Val {
            next = next.Next
        }
        pre.Next = next
        cur = pre
    }
    return dummyHead.Next
}