05 August 2008
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
1
2
Input: 1->1->2
Output: 1->2
Example 2:
1
2
Input: 1->1->2->3->3
Output: 1->2->3
给一个有序链表，检查里面的元素，去重，让每个元素只出现一次。
方法比较清晰，维护两个指针，一个指向当前不重复的最后一个元素，一个进行依次扫描，遇到不重复的则更新第一个指针，继续扫描，否则就把前面指针指向当前元素的下一个（即把当前元素从链表中删除）。
时间上只需要一次扫描，所以是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
/**
* 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) {
return head;
}
ListNode previous = head;
ListNode current = head.next;
while (current != null) {
if (previous.val == current.val) {//有重复，跳过（删掉）current的元素
previous.next = current.next; //current.next如果为null，刚好让尾部不要丢，所以while条件不能是current.next != null
} else {//没有重复，移动previous指针
previous = current;
}
current = current.next;//每次移动current指针
}
return head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode curr = head;
while (curr.next != null) {
if (curr.val == curr.next.val) {
// 删除下一个节点
ListNode temp = curr.next;
curr.next = curr.next.next;
temp.next = null; //将重复的下一个节点指向null
} else {
curr = curr.next;
}
}
return head;
}
}