0082. Remove Duplicates From Sorted List I I | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0082.Remove-Duplicates-from-Sorted-List-II/

[hanlins]

第一层循环遍历不重复的节点，由于我们要在单链表里删除重复的节点，所以我们让慢指针指向前一个节点，遍历他的下一个元素。第二层循环遍历快指针，让他指向链表中上一层被遍历的元素与他值相同最后一个元素。O(n)时间 O(1)空间：

func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    
    for slow, fast := dummy, head; slow.Next != nil; {
        for fast = slow.Next; fast.Next != nil && fast.Next.Val == slow.Next.Val; fast = fast.Next {}
        if slow.Next != fast {
            slow.Next = fast.Next
        } else {
            slow = slow.Next
        }
    }
    
    return dummy.Next
}

[hehelv]

func deleteDuplicates(head *ListNode) *ListNode {
    dummyHead := &ListNode{Next:head}
    p := dummyHead

    for p.Next != nil {
        q := p.Next.Next
        for q != nil && q.Val == p.Next.Val {
            q = q.Next
        }
        if p.Next.Next == q {
            p = p.Next
        } else {
            p.Next = q
        }
    }

    return dummyHead.Next
}