算法与数据结构学习笔记:链表

本文最后更新于:November 28, 2021 am

核心知识点

  • null异常处理

  • dummy node 哑巴节点

  • 双指针/快慢指针

  • 插入一个节点到排序链表

  • 从一个链表中移除一个节点

  • 翻转链表

  • 合并两个链表

  • 找到链表的中间节点

例题:

83. 删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

直接法:

链表是有序的,所以直接更改当前结点的 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
27
28
29
30
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *current=head;
//null异常处理
while(current!=NULL&&current->next!=NULL)
{
//一直删除,直到下一个不重复
// 想想如果把while改成if怎么样
//把current->next!=NULL删除会怎么样
while(current->next!=NULL&&current->val==current->next->val)
{
current->next=current->next->next;
}
//移动到下一个节点
current=current->next;
}
return head;


}
};
  • 时间复杂度:O(n),因为列表中的每个结点都检查一次以确定它是否重复,所以总运行时间为 O(n),其中 n是列表中的结点数。

  • 空间复杂度:O(1),没有使用额外的空间。

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3

利用哑结点

为了防止删除头结点的极端情况发生,先创建空结点dummy,使dummy指向传入的head结点。

然后创建一个cur指针指向dummy,比较cur的后两个结点,看他们是否相同。

如果相同,则说明cur后有重复元素,此时创建一个temp指针指向第一个重复元素,即cur->next;

通过循环进行去重,循环结束后temp指向的是这群重复元素的最后一个,依照题意此时temp的下一个才是我们想要的。

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
//设置哑结点 防止删除头结点的情况发生后的问题
ListNode *dummy=new ListNode(-1);
dummy->next=head;
ListNode *cur=dummy;//cur 指向哑结点

while(cur->next!=NULL&&cur->next->next!=NULL)
{
//比较cur后两个结点
if(cur->next->val==cur->next->next->val)
{
//去重
ListNode *temp=cur->next;
while(temp->next!=NULL&&temp->val==temp->next->val)
{
temp=temp->next;
}
//temp前的重复结点都跳过了,现在我们跳过temp
cur->next=temp->next;
}
else
{
//如果cur后两个结点不重复,直接前移
cur=cur->next;
}
}
return dummy->next;
}
};
  • 时间复杂度:O(n)

  • 空间复杂度:O(1)

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

双指针

如图,定义两个指针,pre在前 cur在后,temp 保存向前的pre指针的临时指针

每次进行一次局部翻转,

当pre到达尾部的时候终止,此时cur指向最后一个节点。

img

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
/*定义两个指针,pre在前 cur在后
*当pre到达尾部的时候终止,此时cur指向最后一个节点
*/
ListNode *pre=head;
ListNode *cur=NULL;
ListNode *temp=NULL;
while(pre!=NULL)
{
temp=pre;//临时存储pre
pre=pre->next;//pre指向下一个节点
temp->next=cur;//翻转指针
cur=temp;//cur指针向前移动一步
}
return cur;

}
};

92. 反转链表 II

反转从位置 mn 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ mn ≤ 链表长度。

示例:

1
2
>输入: 1->2->3->4->5->NULL, m = 2, n = 4
>输出: 1->4->3->2->5->NULL
迭代法:

参考上题,先遍历到 m 处,再翻转

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(head==NULL)
return NULL;

ListNode *pre,*cur;
pre=head;
cur=NULL;

//遍历到m节点,如果只有一个节点,跳过,这里cur会为空但是后面翻转链表的时候就不是了
while(m>1)
{
cur=pre;
pre=pre->next;
m--;
n--;

}

//m节点的前一个节点
ListNode*con=cur;
ListNode*temp=NULL;
//用于保存被翻转链表的第一个节点
ListNode*front=pre;



//反转m-n的节点
while(n--)
{
temp=pre;
pre=pre->next;
temp->next=cur;
cur=temp;
}

//如果不只是一个节点,那么就把指针指向被翻转的链表的最后一个节点
if(con!=NULL)
{
con->next=cur;
}
else
{
//否则直接输出此节点
head=cur;
}
//被翻转的链表原来的头变尾
front->next=pre;
return head;
}
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

迭代法:

直接连接各个节点

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
43
44
45
46
47
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode *dummy=new ListNode(-1);
ListNode *cur=dummy;
//将小的节点接到哑结点为头的链表中
while(l1!=NULL&&l2!=NULL)
{
if(l1->val>l2->val)
{
cur->next=l2;
cur=cur->next;
l2=l2->next;
}
else
{
cur->next=l1;
cur=cur->next;
l1=l1->next;
}

}

//处理剩下的节点
if(l1!=NULL)
{
cur->next=l1;
}
if(l2!=NULL)
{
cur->next=l2;
}
return dummy->next;

}
};

86. 分隔链表

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

当头节点不确定的时候,使用哑巴节点

将大于 x 的节点,放到另外一个链表,最后连接这两个链表

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
43
44
45
46
47
48
49
50
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(head==NULL)
return head;
ListNode *headDummy=new ListNode(-1);
ListNode *tailDummy=new ListNode(-1);
ListNode *cur=NULL,*tail=tailDummy;
headDummy->next=head;

head=headDummy;

while(head->next!=NULL)
{
if(head->next->val<x)
{
head=head->next;
}
//这里把大于X的节点删除,然后连接到另一个链表
else
{
cur=head->next;
//删除大于X的节点
head->next=head->next->next;
//连接到新链表
tail->next=cur;
tail=tail->next;


}
}
//拼接两个链表
//tail代表tailDummy最后一个节点,它的后面可能还连着,要断掉
//如输入[1,4,3,2,5,2]就会有错,没有处理5->2
tail->next=NULL;

head->next=tailDummy->next;
return headDummy->next;


}
};

876. 链表的中间结点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow,*fast;
slow=head;
fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;

}
};

总结:如果链表长度是偶数,返回中间偏右的位置

且fast如果初始化为head->next 返回中间偏左的位置。

奇数长度则两者相同。

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

递归

归并排序链表,找中点和合并操作

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
return mergeSort(head);

}
//寻找链表中点,快慢指针,快的到达终点,慢的刚好到中点
//当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右:
//此题我们让head先走,则停在中间偏左的位置
//148 143 141都有快慢指针
ListNode *findMiddle(ListNode *head)
{
ListNode *slow,*fast;
slow=head;
fast=head->next;
while(fast!=NULL&&fast->next!=NULL)

{
slow=slow->next;
fast=fast->next->next;

}
return slow;
}
//合并两个链表,参考归并排序
ListNode * mergeTwoLists(ListNode*left,ListNode*right)
{
ListNode *dummy=new ListNode(-1);
ListNode *head=dummy;
while(left!=NULL&&right!=NULL)
{
if(left->val>right->val)
{
head->next=right;
right=right->next;
}
else
{
head->next=left;
left=left->next;
}
//下一个
head=head->next;
}
//处理剩下节点
while(left!=NULL)
{
head->next=left;
head=head->next;
left=left->next;
}
while(right!=NULL)
{
head->next=right;
head=head->next;
right=right->next;
}
return dummy->next;
}

ListNode *mergeSort(ListNode *head)
{
if(head==NULL||head->next==NULL)
{
return head;
}

ListNode *middle=findMiddle(head);

// 断开中间节点
ListNode* tail=middle->next;
middle->next=NULL;
//左右分别进行归并排序
ListNode *left=mergeSort(head);
ListNode *right=mergeSort(tail);
ListNode *res=mergeTwoLists(left, right);
return res;
}
};

143. 重排链表

给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

此题目为2019年计算机统考408真题

思路:找到中点断开,翻转后面部分,然后合并前后两个链表

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:

//快慢指针找中点,同上一题
//148 143 141都有快慢指针
ListNode * findMiddle(ListNode *head)
{
ListNode *slow,*fast;
slow=head;
fast=head;
//如果是偶数个节点,返回中间偏右的位置
//你改成fast=head->next返回中间偏左也是对的
//有趣吧,画个图就知道了
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;

}

//合并两个链表
ListNode * mergeTwoLists(ListNode* l1,ListNode*l2)
{
ListNode* dummy=new ListNode(-1);
bool toggle =true;
ListNode *head=dummy;
//间断连接两个链表
while(l1!=NULL&&l2!=NULL)
{
if(toggle)
{
head->next=l1;
l1=l1->next;
}
else
{
head->next=l2;
l2=l2->next;
}
toggle=!toggle;
head=head->next;
}
//连接剩下的节点
while(l1!=NULL)
{
head->next=l1;
l1=l1->next;
head=head->next;

}
while(l2!=NULL)
{
head->next=l2;
l2=l2->next;
head=head->next;

}
return dummy->next;
}

void reorderList(ListNode* head) {
if(head==NULL||head->next==NULL)
return ;

//找到中点 断开
ListNode *middle=findMiddle(head);
ListNode *tail=middle->next;
middle->next=NULL;
//翻转链表
ListNode *cur,*pre;
pre=tail;
cur=NULL;
while(pre!=NULL)
{
ListNode *temp=pre;
pre=pre->next;
temp->next=cur;
cur=temp;
}
tail=cur;

//合并链表
head->next=mergeTwoLists(head,tail)->next;
}

};

141. 环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:true

解释:链表中有一个环,其尾部连接到第二个节点。

img

示例 2:

输入:head = [1,2], pos = 0

输出:true

解释:链表中有一个环,其尾部连接到第一个节点。

img

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

img

快慢指针即可,就像你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她

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.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//148 143 141 142都有快慢指针
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL)
return false;
ListNode *fast,*slow;
slow=head;
fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
// 比较指针是否相等
if(slow==fast)
return true;
}

return false;
}
};

142. 环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例 :

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

img

Floyd 算法

你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她。此题分为两个阶段,第一个阶段先用快慢指针测试是否有环,第二阶段慢指针回到头head,然后各自以相同速度前进,相遇点即为入环处(可以自己画图尝试)。严格的数学证明可参考leetcode官方题解。

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==NULL)
return NULL;
ListNode *slow,*fast;
slow=head;
fast=head;//如果这里是fast=fast->next,那么下面该怎么改?
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//回到起点,各自以相同速度前进
slow=head;
while(slow!=fast)
{
slow=slow->next;
fast=fast->next;

}
return slow;
}
}
return NULL;
}
};

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

1
2
>输入: 1->2
>输出: false

示例 2:

1
2
>输入: 1->2->2->1
>输出: true

先找到链表中点,然后后面的翻转链表,一个个比较。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL)
return true;
ListNode *slow,*fast;
slow=head;
fast=head->next;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
//偶数长度slow是中间偏左的节点
//奇数长度slow是中点

ListNode *cur,*pre,*tail,*temp;
//分离两个链表
tail=slow->next;
slow->next=NULL;
//翻转链表
pre=tail;
cur=NULL;
while(pre!=NULL)
{
temp=pre;
pre=pre->next;
temp->next=cur;
cur=temp;
}
//原链表的最后一个节点现在变成头结点
tail=cur;

while(head!=NULL&&tail!=NULL)
{
if(tail->val!=head->val)
{
return false;
}
head=head->next;
tail=tail->next;

}
return true;

}
};

138. 复制带随机指针的链表

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

复制节点跟在原节点后面即可

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
43
44
45
46
47
48
49
50
51
52
53
54
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/

class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL)
return head;
auto cur=head;
//复制节点到后面
while(cur!=NULL)
{
auto clone=new Node(cur->val);
clone->next=cur->next;
clone->random=cur->random;
cur->next=clone;
cur=clone->next;
}
//处理random指针
cur=head;
while(cur!=NULL)
{
if(cur->random!=NULL)
{
cur->next->random=cur->random->next;
}
cur=cur->next->next;
}
//分离链表
cur=head;
auto cloneHead=cur->next;
while(cur!=NULL&&cur->next!=NULL)
{
auto temp=cur->next;
cur->next=cur->next->next;
cur=temp;

}
return cloneHead;
}
};