首页 > 代码库 > Remove Duplicates from Sorted List II -- LeetCode
Remove Duplicates from Sorted List II -- LeetCode
原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
这道题跟Remove Duplicates from Sorted List比較类似,仅仅是这里要把出现反复的元素所有删除。事实上道理还是一样,仅仅是如今要把前驱指针指向上一个不反复的元素中,假设找到不反复元素,则把前驱指针知道该元素,否则删除此元素。算法仅仅须要一遍扫描。时间复杂度是O(n),空间仅仅须要几个辅助指针,是O(1)。
这道题跟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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。