Remove Duplicates from Sorted List II
今天是一道有關(guān)鏈表的題目水泉，來自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.
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
解題思路
首先秆吵，該題是Remove Duplicates from Sorted List 的升級(jí)版，難度略有加大五慈，但是其實(shí)也并不難纳寂。區(qū)別是主穗，在Remove Duplicates from Sorted List一題中，是對(duì)重復(fù)的數(shù)字只保留一個(gè)毙芜，這里是一個(gè)都不保留忽媒。
然后，了解是上述區(qū)別爷肝，應(yīng)該如何改變算法呢：
在Remove Duplicates from Sorted List一題中我們這樣做猾浦，用一個(gè)指針遍歷整個(gè)鏈表陆错，如果要保留一個(gè)數(shù)字灯抛，則用這個(gè)指針指向的節(jié)點(diǎn)和已經(jīng)加入結(jié)果列表的尾節(jié)點(diǎn)比較，如果相同則跳過音瓷；
在本題中我們不保留重復(fù)的節(jié)點(diǎn)对嚼，那么我們可以用如下方法：
1.首先用一個(gè)循環(huán)跳過相同的節(jié)點(diǎn)；
2.用該節(jié)點(diǎn)和已經(jīng)加入鏈表的尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)比較绳慎，如果相同則加入鏈表纵竖；
3.如果不同，則跳過該節(jié)點(diǎn)杏愤。
好了靡砌，有了上述思路，下面我們來看代碼珊楼。
代碼如下
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;
}
}
關(guān)注我
該公眾號(hào)會(huì)每天推送常見面試題通殃，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助
