首页 > 其他 > 详细

Remove Duplicates from Sorted List II

时间:2014-09-18 05:24:13      阅读:270      评论:0      收藏:0      [点我收藏+]
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

难度:70,参考,现在要把前驱指针指向上一个不重复的元素中,如果找到不重复元素,则把前驱指针知道该元素,否则删除此元素。算法只需要一遍扫描,时间复杂度是O(n),空间只需要几个辅助指针,是O(1)

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode deleteDuplicates(ListNode head) {
14         ListNode dummy = new ListNode(-1);
15         dummy.next = head;
16         ListNode cur = head;
17         ListNode run = dummy;
18         while (cur != null) {
19             while (cur.next != null && run.next.val == cur.next.val) {
20                 cur = cur.next;
21             }
22             if (run.next == cur) {
23                 run = run.next;
24             }
25             else {
26                 run.next = cur.next;
27             }
28             cur = cur.next;
29         }
30         return dummy.next;
31     }
32 }

 

Remove Duplicates from Sorted List II

原文:http://www.cnblogs.com/EdwardLiu/p/3978443.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!