34 链表必备题目（b站左程云）（c++版本）
测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
·
34 链表必备题目
返回两个无环链表的相交的第一个节点
测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
思路
两个链表相交后，就分不开了，他们最后一个非空节点，一定是一样的。让长的先走的，走完多的那一部分。然后两个指针一起走，如果一样就返回。
伪代码
- 如果两个头结点有一个为空，就返回空
- 定义两个节点，遍历两个链表。如果两个节点不相等，说明不相交。比较出哪个链表长
- 把a指向长的链表，把b指向短的链表。
- 让a走长的那部分，然后a,b一起走
代码实现
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL||headB==NULL){
return NULL;
}
ListNode *a=headA;
ListNode *b=headB;
int diff=0;
while(a->next!=NULL){
a=a->next;
diff++;
}
while(b->next!=NULL){
b=b->next;
diff--;
}
if(a!=b){
return NULL;
}
if(diff>=0){
a=headA;
b=headB;
}else{
a=headB;
b=headA;
}
diff=abs(diff);
while(diff--){
a=a->next;
}
while(a!=b){
a=a->next;
b=b->next;
}
return a;
}
};
每k个节点一组翻转链表
测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
思路
就是纯粹的code能力
伪代码
-
定义开始，寻找它的尾。如果尾为空，就返回。
- 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
-
第一组，头结点指向尾，翻转本组链表，开始变成尾，尾变成开始。定义一个LastTeamEnd记录本组的结尾。
- 结尾移动到下一组的头，定义 pre,cur,next。
-
当上一组的尾巴不为空。开始和结尾，反转链表，操作后，LastTeamEnd变成上一组的结尾，上一组的结尾连接到本组的头，上一组结尾记录本组结尾
代码实现
class Solution {
private:
// 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
ListNode* FindEnd(ListNode* a,int num){
while(--num!=0&&a!=nullptr){
//判断s本身，保证找到第k个节点,不会a为空的时候，继续访问下一个
a=a->next;
}
return a;
}
// s -> a -> b -> c -> e -> 下一组的开始节点
// 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
void reverse(ListNode *s,ListNode *e){
e=e->next;
ListNode *pre = nullptr, *cur = s, *next = nullptr;
while (cur != e) {
next = cur->next;
cur->next = pre;//第一个开始前面是置空的
pre = cur;
cur = next;
}
s->next = e;//将第一个前面连接成下一个的头
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *start=head;
ListNode *end=FindEnd(start,k);
if(end==nullptr){
return head;
}
// 第一组很特殊因为牵扯到换头的问题
head=end;//
reverse(start,end);//仅仅是翻转，没有改变start,end的指向
ListNode *LastTeamNode=start;
while(LastTeamNode->next!=nullptr){
start=LastTeamNode->next;
end=FindEnd(start,k);
if(end==nullptr){
return head;
};
reverse(start,end);
LastTeamNode->next=end;
LastTeamNode=start;
}
return head;
}
};
复制带随机指针的链表
思路
仿照哈希表，实现功能
伪代码
-
1 -> 2 -> 3 -> … 变成 : 1 -> 1’ -> 2 -> 2’ -> 3 -> 3’ -> …
-
利用上面新老节点的结构关系，设置每一个新节点的random指针
-
新老链表分离 : 老链表重新连在一起，新链表重新连在一起
代码实现
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL){
return NULL;
}
Node *cur=head;
Node *next=NULL;
// 1 -> 2 -> 3 -> ...
// 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ...
while(cur!=NULL){
next=cur->next;
cur->next=new Node(cur->val);//连接新结点
cur->next->next=next;
cur=next;
}
cur=head;
Node *copy=NULL;
// 利用上面新老节点的结构关系，设置每一个新节点的random指针
while(cur!=NULL){
next=cur->next->next;
copy=cur->next;
copy->random=cur->random==NULL?NULL:cur->random->next;
cur=next;
}
cur=head;
Node *ans=cur->next;//ans是新的头结点
while(cur!=NULL){
next=cur->next->next;
copy=cur->next;//用copy连接新链表
cur->next=next;
copy->next=next==NULL?NULL:next->next;
cur=next;
}
return ans;
}
};
判断链表是否为回文结构
测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
思路
- 快慢指针找中点
- 从左侧和右侧开始比较
伪代码
- 特例判断，如果头结点为空或者只有一个结点，返回真
- 定义快慢指针，慢指针一次走一步，快指针一次走两步。（无论奇数偶数都可以）
- 现在中点就是slow，从中点开始往后的节点逆序
- 从左侧和右侧往中间指，每一步对比值是否一样，如果不一样答案就是false
- 把链表恢复成原来的样子
代码实现
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return true;
}
// 找中点
ListNode *fast=head,*slow=head;
while(fast->next!=nullptr&&fast->next->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
// 现在中点就是slow，从中点开始往后的节点逆序
ListNode *pre=slow,*cur=pre->next,*next=nullptr;
pre->next=nullptr;
while(cur!=nullptr){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
// 上面的过程已经把链表调整成从左右两侧往中间指
// head -> ... -> slow <- ... <- pre
//pre移动完后，来到了链表的末尾
bool ans=true;
ListNode *left=head,*right=pre;
// left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是false
while(left!=nullptr&&right!=nullptr){
if(left->val!=right->val){
ans=false;
break;
}
left=left->next;
right=right->next;
}
// 本着不坑的原则，把链表调整回原来的样子再返回判断结果
cur=pre->next;
pre->next=nullptr;
next=nullptr;
while(cur!=nullptr){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return ans;
}
};
返回链表的第一个入环结点
测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
思路
背
伪代码
- 特例判断，头结点为空，头结点下一个为空，或者下下为空，返回空
- 定义快慢指针，当快慢指针相遇时，快指针回到头结点。如果快指针指向为空，说明无环，返回空。
- 快慢指针都走一步，当他们相遇时，就是第一个入环结点
代码实现
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==nullptr||head->next==nullptr||head->next->next==nullptr){
return nullptr;//为快指针做准备
}
ListNode *fast=head->next->next;
ListNode *slow=head->next;
while(fast!=slow){
if(fast->next==nullptr||fast->next->next==nullptr){
return nullptr;
}
fast=fast->next->next;
slow=slow->next;
}
fast=head;
while(fast!=slow){
fast=fast->next;
slow=slow->next;
}
return slow;
}
};
排序链表
要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
数组排序做不到，链表排序可以
测试链接 : https://leetcode.cn/problems/sort-list/
思路
归并分治
伪代码
-
数出数组的长度，定义l1,r1,l2,r2,next,lastTeamEnd
-
步长，因为第一组涉及到整个链表的头的问题，要单独处理
-
分配好l,r,next的位置,让r1,r2的next置空，如果要单独处理，断连最保险。merge左右两个链表，头结点来到merge完的start，lasrTeamEnd来到末尾
- 定义pre,连接链表，第一组特殊，涉及到start的位置，单独处理。比较l1和l2的值，谁小pre就连接谁。l1或者12遍历完一条后，将剩余的连接上，end来到连接完成的末尾
-
head来到start,lastTeamEnd来到end
-
循环连接剩下当前步长下，未处理的结点。
代码实现
class Solution {
// 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
// 注意为了额外空间复杂度O(1)，所以不能使用递归
// 因为mergeSort递归需要O(log n)的额外空间
public:
ListNode* sortList(ListNode* head) {
int n=0;
ListNode *cur=head;
while(cur!=nullptr){
n++;
cur=cur->next;
}
// l1...r1 每组的左部分
// l2...r2 每组的右部分
// next 下一组的开头
// lastTeamEnd 上一组的结尾
ListNode *l1,*r1,*l2,*r2,*next,*lastTeamEnd;
ListNode *start=nullptr,*end=nullptr;
for(int step=1;step<n;step<<=1){
// 第一组很特殊，因为要决定整个链表的头，所以单独处理
l1=head;
r1=findEnd(l1,step);
l2=r1->next;
if(l2==nullptr){
break;
}
r2=findEnd(l2,step);
next=r2->next;
r1->next=nullptr;//让他们断连，如果要单独处理，断连最保险
r2->next=nullptr;//让他们断连
merge(l1,r1,l2,r2,start,end);
head=start;
lastTeamEnd=end;
while(next!=nullptr){
l1=next;
r1=findEnd(l1,step);
l2=r1->next;
if(l2==nullptr){
lastTeamEnd->next=l1;
break;
}
//如果l2为空，说明右侧已经没有元素，无需再执行merge
//左侧未merge的元素，会在某一个步长时merge，而且不会混在已经merge的元素里面
r2=findEnd(l2,step);
next=r2->next;
r1->next=nullptr;
r2->next=nullptr;
merge(l1,r1,l2,r2,start,end);
lastTeamEnd->next=start;
lastTeamEnd=end;
}
}
return head;
}
private:
// 包括s在内，往下数k个节点返回
// 如果不够，返回最后一个数到的非空节点
ListNode* findEnd(ListNode* s,int k){
if (s == nullptr) {
return nullptr;
}
while(--k!=0&&s->next!=nullptr){
s=s->next;
}
return s;
}
// l1...r1 -> null : 有序的左部分
// l2...r2 -> null : 有序的右部分
// 整体merge在一起，保证有序
// 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
void merge(ListNode *l1,ListNode *r1,ListNode *l2,ListNode *r2,ListNode*& start, ListNode*& end){
// 空指针防护：其中一组为空，直接返回另一组
if (l1 == nullptr) {
start = l2;
end = r2;
return;
}if (l2 == nullptr) {
start = l1;
end = r1;
return;
}
ListNode *pre=nullptr;
if(l1->val<=l2->val){
start=l1;
pre=l1;
l1=l1->next;
}else{
start=l2;
pre=l2;
l2=l2->next;
}
while(l1!=nullptr&&l2!=nullptr){
if(l1->val<=l2->val){
pre->next=l1;
pre=l1;
l1=l1->next;
}else{
pre->next=l2;
pre=l2;
l2=l2->next;
}
}
if(l1!=nullptr){
pre->next=l1;
end=r1;
}else{
pre->next=l2;
end=r2;
}
}
};
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)