链表(一)基础操作
环形链表插值
题目
有一个整数val,如何在节点值有序的环形链表中插入一个节点值为val的节点,并且保证这个环形单链表依然有序。
给定链表的信息,及元素的值A及对应的nxt指向的元素编号同时给定val,请构造出这个环形链表,并插入该值。
输入:[1,3,4,5,7],[1,2,3,4,0],2
返回:{1,2,3,4,5,7}
代码
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
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class InsertValue {
public:
ListNode *insert(vector<int> A, vector<int> nxt, int val) {
// write code here
ListNode *phead = createList(A, nxt);
if (!phead) {
phead = new ListNode(val);
phead->next = phead;
return phead;
}
ListNode *pnode = phead;
while (val > pnode->val) {
pnode = pnode->next;
if (pnode == phead)break;
}
ListNode *ptep = new ListNode(pnode->val);
ptep->next = pnode->next;
pnode->next = ptep;
pnode->val = val;
if (phead == pnode) return (pnode->val > ptep->val ? ptep : phead);
else return phead;
}
ListNode *createList(const vector<int> &val, const vector<int> &nxt) {
if (val.empty() || nxt.empty() || val.size() != nxt.size())
return nullptr;
ListNode *head = new ListNode(val[0]);
ListNode *node = head;
vector<int>::size_type index = 0;
for (index = 0; index < nxt.size(); index++) {
node->next = new ListNode(val[nxt[index]]);
node = node->next;
}
node->next = head->next;
ListNode *p = head;
head = node;
delete p;
return head;
}
void printList(const ListNode *head) {
ListNode *p;
if (head) {
cout << head->val << endl;
for (p = head->next; p != head; p = p->next) {
cout << p->val << endl;
}
}
}
};
int main() {
vector<int> A = {1, 3, 4, 5, 7};
vector<int> nxt = {1, 2, 3, 4, 0};
ListNode *p = nullptr;
InsertValue ins;
p = ins.insert(A, nxt, 0);
ins.printList(p);
return 0;
}
注意
如何在当前节点之后插入一个值:
- 分配一个节点,将插入值存入该节点
- 插入节点的next指向当前节点的next;当前节点的next指向插入节点。
如何在当前节点之前插入一个值:
- 分配一个节点,值为当前节点的复制
- 新增节点的next指向当前节点的next;
- 当前节点的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
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
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Remove {
public:
ListNode *removeNode(ListNode *pHead, int delVal) {
// write code here
if (!pHead)return pHead;
if (pHead->val == delVal) {
ListNode *p = pHead->next;
pHead->next=NULL;
delete pHead;
return p;
}
ListNode *cur = pHead->next;
ListNode *pre = pHead;
while (cur != NULL) {
if (cur->val == delVal) {
pre->next = cur->next;
cur->next = NULL;
delete cur;
break;
}
cur = cur->next;
pre = pre->next;
}
return pHead;
}
ListNode *createList(const vector<int> &A) {
if (A.empty())return nullptr;
ListNode *phead = new ListNode(A[0]);
ListNode *pnode = phead;
for (vector<int>::size_type index = 1; index < A.size(); index++) {
ListNode *ptmp = new ListNode(A[index]);
pnode->next = ptmp;
pnode = ptmp;
}
return phead;
}
void printList(ListNode *phead) {
ListNode *p = phead;
if (p) {
cout << p->val << endl;
p = p->next;
while (p) {
cout << p->val << endl;
p = p->next;
}
}
cout << endl;
}
};
int main() {
vector<int> A{0, 1, 2, 3, 4};
Remove R;
ListNode *p = NULL;
p = R.createList(A);
R.printList(p);
p = R.removeNode(p, 0);
R.printList(p);
return 0;
}
注意
假定只能访问删除节点,不能访问删除节点的前一个节点,如何删除
- 如果删除节点的后一个节点不为空,则可以将后一个节点的值复制到待删除节点的值,然后将待删除节点指向后一个节点的后一个节点,删除后一个节点即可
- 如果删除节点为最后一个节点,则不能删除,会引起系统错误;
链表(二)习题
链表的分化练习题
题目
对于一个链表,我们需要用一个特定阈值完成对它的分化,使得小于等于这个值的结点移到前面,大于该值的结点在后面,同时保证两类结点内部的位置关系不变。
给定一个链表的头结点head,同时给定阈值val,请返回一个链表,使小于等于它的结点在前,大于等于它的在后,保证结点值不重复。
{1,4,2,5},3
{1,2,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
36class Divide {
public:
ListNode *listDivide(ListNode *head, int val) {
// write code here
ListNode *maxhead = NULL;
ListNode *maxtail = NULL;
ListNode *minhead = NULL;
ListNode *mintail = NULL;
ListNode *pnext = NULL;
while (head) {
pnext = head->next;
head->next = NULL;
if (head->val <= val) {
if (minhead == NULL) {
minhead = head;
mintail = head;
} else {
mintail->next = head;
mintail = head;
}
} else {
if(maxhead == NULL){
maxhead = head;
maxtail = head;
}else{
maxtail->next = head;
maxtail = head;
}
}
head = pnext;
}
if(mintail !=NULL)
mintail->next = maxhead;
return minhead!=NULL? minhead: maxhead;
}
};
打印两个链表的公共值
题目
现有两个升序链表,且链表中均无重复元素。请设计一个高效的算法,打印两个链表的公共值部分。
给定两个链表的头指针headA和headB,请返回一个vector,元素为两个链表的公共部分。请保证返回数组的升序。两个链表的元素个数均小于等于500。保证一定有公共值
{1,2,3,4,5,6,7},{2,4,6,8,10}
返回:[2.4.6]
过程
- 如果两个链表其中有一个为空,则返回;
- 两个指针分别指向两个链表,如果链表1的值小于链表2的值,则链表1往后移动一个位置
- 如果链表2的值小于链表1的值,则链表2往后移动一个位置
- 如果值相等,把值存入vector,然后两个链表都往后移动一个位置。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Common {
public:
vector<int> findCommonParts(ListNode* headA, ListNode* headB) {
// write code here
vector<int> ret;
ListNode* pa=headA;
ListNode* pb=headB;
if(pa==NULL || pb==NULL)return;
while(pa!=NULL&&pb!=NULL){
if(pa->val<pb->val)pa=pa->next;
else if(pa->val>pb->val)pb=pb->next;
else{
ret.push_back(pa->val);
pa=pa->next;
pb=pb->next;
}
}
return ret;
}
};
链表的K逆序练习
题目
有一个单链表,请设计一个算法,使得每K个节点之间逆序,如果最后不够K个节点一组,则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null,K=3这个例子。调整后为,3->2->1->6->5->4->7->8->null。因为K==3,所以每三个节点之间逆序,但其中的7,8不调整,因为只有两个节点不够一组。
给定一个单链表的头指针head,同时给定K值,返回逆序后的链表的头指针。
过程
- 根据区间的程度K求出每一个区段的前一个值,后一个值,开始值,结束值
- 然后进行逆序
代码
1 |
|
链表指定值清除
题目
现在有一个单链表。链表中每个节点保存一个整数,再给定一个值val,把所有等于val的节点删掉。
给定一个单链表的头结点head,同时给定一个值val,请返回清除后的链表的头结点,保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。
过程
- 删除前几个为指定值的节点,将头节点移动到第一个不为删除值的节点;
- 用pre制定为不为val的节点,cur指向pre的后一个节点,如果cur为val,则pre的next指向cur的next;否则pre指向cur; 然后cur跳为下一个;
代码
1 | class ClearValue { |
链表回文结构
题目
请编写一个函数,检查链表是否为回文。
给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。
过程
方法一
- 遍历链表,将链表的每一个元素压入到栈中;
- 第二次遍历链表,比较每一个值和栈中弹出值,如果遇到不相等的则不是回文
方法二
- 定义快慢指针, 快指针一次走两个,慢指针一次走一个,将慢指针的值压入到栈中
- 如果快指针的下一个值为空,则为奇数个,应该弹出一个栈顶元素
- 慢指针依次向后遍历,比较栈顶元素和链表值,如果遇到不相等的,则不是回文
方法三
- 定义快慢指针,定义快慢指针, 快指针一次走两个,慢指针一次走一个,找到中间值
- 将中间值往后的链表元素进行逆转
- 从两头往中间遍历链表,比较对应的元素,如果出现不相等的,则不是回文
代码
1 | class Palindrome { |
链表(三)习题
复杂链表的复制练习题
题目
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。
过程
- 遍历链表,将链表复制一份
- 遍历节点,拿到一对拷贝,拷贝的链表的random为链表的random,找到random指向的链表,将拷贝链表的random指向链表的下一个
- 将两个链表分离
代码
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/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead == NULL)return NULL;
RandomListNode* cur = pHead;
RandomListNode* next = NULL;
while(cur != NULL){
next = cur->next;
cur->next = new RandomListNode(cur->label);
cur->next->next = next;
cur = next;
}
cur = pHead;
RandomListNode* curCopy = NULL;
while(cur != NULL){
next = cur->next->next;
curCopy = cur->next;
curCopy->random = cur->random != NULL ? cur->random->next : NULL;
cur = next;
}
cur = pHead;
RandomListNode* res = pHead->next;
while(cur != NULL){
next = cur->next->next;
curCopy = cur->next;
cur->next = next;
curCopy->next = next != NULL ? next->next : NULL;
cur = next;
}
return res;
}
};
链表判断环
题目
如何判断一个单链表是否有环?有环的话返回进入环的第一个节点的值,无环的话返回-1。如果链表的长度为N,请做到时间复杂度O(N),额外空间复杂度O(1)。
给定一个单链表的头结点head(注意另一个参数adjust为加密后的数据调整参数,方便数据设置,与本题求解无关),请返回所求值。
过程
- 定义快慢指针,依次遍历,当快慢指针相等时候,则认定链表又环,如果没有相等,则没有环
- 如果链表有环,则将快指针指向头,慢指针从原来位置继续遍历,每一次遍历一个,知道两个指针相等,返回指针的值即可
代码
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/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class ChkLoop {
public:
int chkLoop(ListNode* head, int adjust) {
// write code here
if(head == NULL || head->next == NULL)return -1;
ListNode* pfastnode = head;
ListNode* pslownode = head;
while(pfastnode != NULL && pfastnode->next !=NULL){
pslownode = pslownode->next;
pfastnode = pfastnode->next->next;
if(pslownode == pfastnode)break;
}
if(pslownode == pfastnode){
pfastnode = head;
while(pfastnode != pslownode){
pfastnode = pfastnode->next;
pslownode = pslownode->next;
}
return pfastnode->val;
}else{
return -1;
}
}
};
无环单链表相交
题目
现在有两个无环单链表,若两个链表的长度分别为m和n,请设计一个时间复杂度为O(n + m),额外空间复杂度为O(1)的算法,判断这两个链表是否相交。
给定两个链表的头结点headA和headB,请返回一个bool值,代表这两个链表是否相交。保证两个链表长度小于等于500。
过程
方法一
- 将链表A节点存入hash表中,遍历链表B,看是否存在对应B元素在hash表中存在
方法二
- 先遍历两个链表,求出两个链表的长度
- 将较长的链表先遍历长度差值,剩下两个长度相同的链表
- 同时遍历,如果相交,则在同一节点相遇,两节点指针相同
代码
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/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class CheckIntersect {
public:
bool chkIntersect(ListNode* headA, ListNode* headB) {
// write code here
ListNode* pa = headA;
ListNode* pb = headB;
if(pa==NULL || pb == NULL)return false;
int countA=0, countB=0;
while(pa != NULL){
pa = pa->next;
countA++;
}
while(pb != NULL){
pb = pb->next;
countB++;
}
int countC = countA>countB?countA-countB:countB-countA;
pa=headA;pb=headB;
while(countC){
if(countA>countB){
pa=pa->next;
countC--;
}else{
pb=pb->next;
countC--;
}
}
while(pa!=NULL&&pb!=NULL){
if(pa == pb)return true;
pa=pa->next;
pb=pb->next;
}
return false;
}
};
有环单链表相交
题目
如何判断两个有环单链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。如果两个链表长度分别为N和M,请做到时间复杂度O(N+M),额外空间复杂度O(1)。
给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。过程
- 先利用快慢指针分别求出两个有环链表的入环节点,如果两个入环节点相等,则返回true
- 从链表1的入环节点开始往下遍历,如果遇到为start1,则无相交,如果遇到start2,则相交
代码
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/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class ChkIntersection {
public:
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
// write code here
ListNode* start1 = enterHuan(head1);
ListNode* start2 = enterHuan(head2);
if(start1 == start2)return true;
ListNode* p=start1->next;
while(p!=start1&&p!=start2)
p = p->next;
if(p == start2)
return true;
return false;
}
ListNode* enterHuan(ListNode* head){
ListNode* pfastnode=head;
ListNode* pslownode=head;
while(pfastnode&&pfastnode->next){
pfastnode = pfastnode->next->next;
pslownode = pslownode->next;
if(pfastnode == pslownode)break;
}
if(pfastnode == pslownode){
pfastnode = head;
while(pfastnode != pslownode){
pfastnode = pfastnode->next;
pslownode = pslownode->next;
}
return pslownode;
}else{
return NULL;
}
}
};
单链表相交
题目
给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。
给定两个链表的头结点head1和head2(注意,另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。
过程
- 判断链表是否有环,有环返回入环,无环则返回空
- 如果一个有环,一个无环,则不可能相交
- 如果两个都无环,则按照无环链表相交判断
- 如果两个都有环,则按照有环链表相交判断
代码
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
99
100
101
102
103
104/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class ChkIntersection {
public:
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
// write code here
ListNode* p1 = chkLoop(head1);
ListNode* p2 = chkLoop(head2);
if((p1==NULL&&p2!=NULL) ||(p1!=NULL&&p2==NULL))return false;
if(p1 == NULL && p2 == NULL)return chkIntersect(head1, head2);
else return chkInter(head1, head2);
}
//判断是否有环
ListNode* chkLoop(ListNode* head) {
// write code here
if(head == NULL || head->next == NULL)return NULL;
ListNode* pfastnode = head;
ListNode* pslownode = head;
while(pfastnode != NULL && pfastnode->next !=NULL){
pslownode = pslownode->next;
pfastnode = pfastnode->next->next;
if(pslownode == pfastnode)break;
}
if(pslownode == pfastnode){
pfastnode = head;
while(pfastnode != pslownode){
pfastnode = pfastnode->next;
pslownode = pslownode->next;
}
return pfastnode;
}else{
return NULL;
}
}
//无环链表相交
bool chkIntersect(ListNode* headA, ListNode* headB) {
// write code here
ListNode* pa = headA;
ListNode* pb = headB;
if(pa==NULL || pb == NULL)return false;
int countA=0, countB=0;
while(pa != NULL){
pa = pa->next;
countA++;
}
while(pb != NULL){
pb = pb->next;
countB++;
}
int countC = countA>countB?countA-countB:countB-countA;
pa=headA;pb=headB;
while(countC){
if(countA>countB){
pa=pa->next;
countC--;
}else{
pb=pb->next;
countC--;
}
}
while(pa!=NULL&&pb!=NULL){
if(pa == pb)return true;
pa=pa->next;
pb=pb->next;
}
return false;
}
//有环链表是否相交
bool chkInter(ListNode* head1, ListNode* head2) {
// write code here
ListNode* start1 = enterHuan(head1);
ListNode* start2 = enterHuan(head2);
if(start1 == start2)return true;
ListNode* p=start1->next;
while(p!=start1&&p!=start2)
p = p->next;
if(p == start2)
return true;
return false;
}
ListNode* enterHuan(ListNode* head){
ListNode* pfastnode=head;
ListNode* pslownode=head;
while(pfastnode&&pfastnode->next){
pfastnode = pfastnode->next->next;
pslownode = pslownode->next;
if(pfastnode == pslownode)break;
}
if(pfastnode == pslownode){
pfastnode = head;
while(pfastnode != pslownode){
pfastnode = pfastnode->next;
pslownode = pslownode->next;
}
return pslownode;
}else{
return NULL;
}
}
};