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
|
Solution 1:
- 遍历一遍数组，依次比较相邻的两个元素，同时，设定一个tag
isSame 来保存上两个元素是否一样
- 如果上两个元素一样，指针
p q 往后移一位，继续
- 如果两个元素不一样，将
p加入到待返回的列表中，继续
- 循环结束时，
isSame中保存了最后一次的比较情况，如果最后一次结果一样，返回列表的最后需要加上null 如果最后一次结果不一样，需要将p之后的元素都添加到返回列表中。
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
35
36
37
38
39
40
41
42
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
boolean isSame = false;
ListNode dump = new ListNode(0);
ListNode t = dump;
if (head == null || head.next == null){
return head;
}
ListNode p = head;
ListNode q = head.next;
while(q != null){
while (q != null && p.val == q.val){
isSame = true;
p = p.next;
q = q.next;
}
if (q == null){
break;
}
if (isSame){
p = p.next;
q = q.next;
isSame = false;
}
else {
t.next = p;
t = t.next;
p = p.next;
q = q.next;
}
}
if (! isSame){
t.next = p;
}
if (isSame){
t.next = null;
}
return dump.next;
}
}
|
Solution 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public ListNode deleteDuplicates(ListNode head) {
if(head==null) return null;
ListNode FakeHead=new ListNode(0);
FakeHead.next=head;
ListNode pre=FakeHead;
ListNode cur=head;
while(cur!=null){
while(cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
if(pre.next==cur){
pre=pre.next;
}
else{
pre.next=cur.next;
}
cur=cur.next;
}
return FakeHead.next;
}
|
