本文为剑指 offer 系列第五十三篇。
主要知识点为链表的遍历，去除重复元素。
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
解题思路
思路1
将整个链表进行遍历，通过map来保存每个节点出现的次数。之后再重建链表，链表结点的值仅仅对应于出现一次的元素。返回新链表即可。
思路2
可以直接在原来的链表上进行操作，具体的思路如下：
首先在头节点之前建立一个帮助结点，帮助结点之后的就是我们真正的没有重复结点的链表。
然后我们从head结点开始向后遍历，如果碰到有相同元素，那么一直向后遍历，越过这些重复元素。如果元素值没有重复，那么就都向后遍历一个节点。直到遍历结束。
下面以1->2->3->3->4->4->5为例进行详细说明，
我们开始创建辅助节点将原来的链表变成-1->1->2->3->3->4->4->5,
然后有两个指针一个指针p指向之前的头节点1，一个指针last指向辅助节点-1，开始遍历。提醒一下，他们两个操作的可是同一个链表。
- 1!=2,所以1不重复，所以p前移指向2，last前移指向1；
- 2!=3,所以2不重复，所以p前移指向3，last前移指向2；
- 3==3，所以3是重复的，这个时候p继续前移，直到指向第一个不是3的节点，也就是4，last的next指向4.（这样的话所有的3就已经被删除了）
- 4==4，所以4也是重复的，这个时候p继续前移，直到指向第一个不是4的节点，也就是5，last的next指向5，(这样的话所有的4就已经被删除了)
- 5已经没有后继节点了，所有结束。
然后整个的链表就变成了-1->1->2->5,最后结果返回-1的next即可。
相比于前一种思路可以极大的提高空间同时提升效率。
扩展
本题目的目标是1->2->3->3->4->4->5变成1->2->5，题目等同于leetcode-83-RemoveDuplicatesfromSortedListII
但是也有类似的题目是从1->2->3->3->4->4->5变成1->2->3->4->5。比如leetcode-82-RemoveDuplicatesfromSortedList
解题代码
思路2代码
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
| /*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head)
{
ListNode* first = new ListNode(-1);
first->next = head;
ListNode* last = first;
ListNode* p = head;
while(p && p->next){
if(p->val == p->next->val){
//如果有重复元素，那么就跳过。
int val = p->val;
while(p && p->val == val){
p = p->next;
}
//此时p指向不是之前相等值的第一个元素，但是不能保证这个值也不重复，
//所以此时继续进入到循环之中进行判断。
//通过last->next = p 删除了中间值为val的所有值。
last->next = p;
}else{
// 如果不重复，那就直接链接到last上。p继续后移
last= p;
p = p->next;
}
}
return first->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
| /*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(!pHead) return NULL;
ListNode* p = pHead;
ListNode* first = new ListNode(-1);
first->next = pHead;
ListNode* tail = first;
while(p){
if((p->next && p->val != p->next->val) || !p->next){
tail = p;
p = p->next;
}else{
int a = p->val;
while(p && p->val == a){
p = p->next;
}
tail->next = p;
}
}
return first->next;
}
};
|
扩展代码
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
| /*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head)
{
// 去掉重复元素,重复元素保留一次
if(!head) return NULL;
ListNode* p = head;
while(p && p->next){
if(p->val == p->next->val){
p->next = p->next->next;
}else{
p = p->next;
}
}
return head;
}
};
|
时间复杂度为O(n),空间复杂度为O(1)
以上，本题结束！