Remove Duplicates from Sorted List II
今天是一道有关链表的题目，来自LeetCode，难度为Medium，Acceptance为27%。
题目如下
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example
Given1->2->3->3->4->4->5, return1->2->5.
Given1->1->1->2->3, return2->3.
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
首先，该题是Remove Duplicates from Sorted List 的升级版，难度略有加大，但是其实也并不难。区别是，在Remove Duplicates from Sorted List一题中，是对重复的数字只保留一个，这里是一个都不保留。
然后，了解是上述区别，应该如何改变算法呢：
在Remove Duplicates from Sorted List一题中我们这样做，用一个指针遍历整个链表，如果要保留一个数字，则用这个指针指向的节点和已经加入结果列表的尾节点比较，如果相同则跳过；
在本题中我们不保留重复的节点，那么我们可以用如下方法：
1.首先用一个循环跳过相同的节点；
2.用该节点和已经加入链表的尾节点的下一个节点比较，如果相同则加入链表；
3.如果不同，则跳过该节点。
好了，有了上述思路，下面我们来看代码。
代码如下
Java版
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @return: ListNode head of the linked list
*/
public static ListNode deleteDuplicates(ListNode head) {
// write your code here
if(null == head)
return null;
ListNode newHead = new ListNode(0), p = newHead, fast = head;
newHead.next = head;
while(fast != null) {
while(fast.next != null && fast.val == fast.next.val) {
fast = fast.next;
}
if(p.next == fast) {
p = p.next;
} else {
p.next = fast.next;
}
fast = fast.next;
}
p.next = null;
return newHead.next;
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
image
