Remove Duplicates from Sorted List

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/41728739

Given a sorted linked list, delete all duplicates such that each element appear only once.

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

思路:

(1)题意为移除已排序链表中重复元素。

(2)首先,对头结点进行判空,为空则返回空。不为空设定first指向head。

(3)其次,判断first的后续节点second是不是为空,如果不为空,则比较它们值是不是相同。如果值不同,则节点first指向second,

         second指向first的后续节点,循环继续;如果值相同,设置节点last指向second的后续节点,如果last不为空,并且last的值

         和first的值相同(说明连续3个节点值相同),last指向其后续节点,循环直到ast为空或first的值和last的值不同,此时,

         如果last不为空,则first的后续节点为last,first指向last,second指向first的后续位置,循环继续,如果last为空,说明已

         遍历到最后节点,此first的后续节点指向null,返回head。

(4)其指向进程可以简单以下所示:
         例如:1->1->2->3->3->3->4->5->5->5
                  (A)first=1,second=1,first=second,则last=2,由于first!=last,所以first=2,second=3;
                  (B)first=2,second=3,first!=second,则first=3,second=3;
                  (C)first=3,second=3,first=second,则last=3,由于first=last,循环直到last==null或first!=last,此时last=4,则first=4,second=5;
                  (D)first=4,second=5,first!=second,则first=5,last=5;
                  (E)first=5,last=5,first=second,last=5,由于first=last,循环直到last==null或first!=last,此时last=null,则first.next=null,返回head


算法代码实现以下:

public ListNode deleteDuplicates(ListNode head) {
if (head == null)
return null;
ListNode first = head;
ListNode second = first.next;
while (second != null) {
if (first.val == second.val) {
ListNode last = second.next;
while (last != null && first.val == last.val) {
last = last.next;
}
if (last != null) {
first.next = last;
first = last;
second = first.next;
} else {
first.next=null;
return head;
}

} else {
first = second;
second = first.next;
}
}
return head;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Remove Duplicates from Sorted List

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡