程序员人生网站导航

Remove Duplicates from Sorted List

栏目：php教程时间：2014-12-17 08:08:23

本文是在学习中的总结，欢迎转载但请注明出处：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; }

------分隔线----------------------------

上一篇 设计模式之桥接模式

下一篇 程序员怎能不知道什么是数据挖掘

------分隔线----------------------------