05 August 2008
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
1
2
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
1
2
Input: 1->1->1->2->3
Output: 2->3
给一个链表，检查里面的元素，移除所有有重复的元素，只要重复就一个不留，不重复的保留。这道题与83题的区别就是要把所有重复的node删除。因此，还是利用I中去重的方法，引用双指针，遍历链表，注意这里建立一个dummy head，让dummy head的next指向head，这样最后返回就是dummy.next就行。
同样，时间上只需要一次扫描，所以是O(n)，空间上两个额外指针，O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, curr = head;
while (curr != null) {
while (curr.next != null && curr.val == curr.next.val) { //当前值和next值重复
curr = curr.next;
}
if (prev.next == curr) { //上面的while循环没有找到重复值
prev = prev.next;
} else { // curr继续去找可能的重复值
prev.next = curr.next; //将上面while循环的重复值都删掉，暂时将prev头接到curr位置
}
curr = curr.next; // curr = prev.next也可以，从另外一条路过来
}
return dummy.next;
}
}
也可以用递归的办法，每次判断重复或者不重复，进行相应地递归调用。Recursive调用n层，时间为O(n)，空间为O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.val != head.next.val) {
head.next = deleteDuplicates(head.next); // 没重复，直接调用下一个节点，返回当前head
return head;
} else {
while (head.next != null && head.val == head.next.val) {
head = head.next; //有重复，直接抛弃
}
return deleteDuplicates(head.next); // 抛弃最后一个重复的节点，返回下一个节点
}
}
}