首页 > 代码库 > Remove Duplicates from Sorted List II -- LeetCode

Remove Duplicates from Sorted List II -- LeetCode

2024-10-28 14:47:39   212人阅读

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ 
这道题跟Remove Duplicates from Sorted List比較类似，仅仅是这里要把出现反复的元素所有删除。事实上道理还是一样，仅仅是如今要把前驱指针指向上一个不反复的元素中，假设找到不反复元素，则把前驱指针知道该元素，否则删除此元素。算法仅仅须要一遍扫描。时间复杂度是O(n)，空间仅仅须要几个辅助指针，是O(1)。

代码例如以下： 

public ListNode deleteDuplicates(ListNode head) {
    if(head == null)
        return head;
    ListNode helper = new ListNode(0);
    helper.next = head;
    ListNode pre = helper;
    ListNode cur = head;
    while(cur!=null)
    {
        while(cur.next!=null && pre.next.val==cur.next.val)
        {
            cur = cur.next;
        }
        if(pre.next==cur)
        {
            pre = pre.next;
        }
        else
        {
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    
    return helper.next;
}
能够看到，上述代码中我们创建了一个辅助的头指针。是为了改动链表头的方便。前面介绍过，通常会改到链表头的题目就会须要一个辅助指针，是比較常见的技巧。

Remove Duplicates from Sorted List II -- LeetCode


联系
我们