您现在的位置是：首页 >学无止境 >day4 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、 142.环形链表II网站首页学无止境
day4 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、 142.环形链表II
目录：
链接
题目链接：
https://leetcode.cn/problems/swap-nodes-in-pairs/
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
https://leetcode.cn/problems/linked-list-cycle-ii/
解题及思路学习
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WW55AwAZ-1685353234158)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f8f59f5e-54f6-4786-8fbf-16f18602a402/Untitled.png)]
自己想法：可以拆分为交换两个相邻节点。只有一个或者没有节点时，不交换。可以用两个指针来分别表示前后两个节点。应该还需要一个节点来暂存后面的值。
自己想法的代码实现：
（有点绕，下次遇见这种，可以拿张草稿纸画一下）
/**
* 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* swapPairs(ListNode* head) {
ListNode* pre;
ListNode* cur;
ListNode* dummyHead = new ListNode(0);
dummyHead -> next = head;
pre = dummyHead;
cur = head;
ListNode* tmp;
while(cur != NULL && cur -> next != NULL){
pre ->next =cur -> next;
tmp = cur -> next -> next;
pre -> next -> next = cur;
cur -> next = tmp;
pre = cur;
cur = cur -> next;
}
tmp = dummyHead -> next;
delete dummyHead;
return tmp;
}
};
随想录想法：步骤差不多，不过是用一个指针cur和两个临时指针来分别表示cur前面一个和后面一个节点。
代码实现：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
其实两种方法的思路都差不多，不过代码随想录的方法更加简洁，不容易绕晕。一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lmqBLS3e-1685353234162)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ac022418-b4c3-488b-8f50-97ed27d7879a/Untitled.png)]
自己思路：删除倒数第n个，对于单链表来说，得先知道长度吧。先确定范围，n是要小于整个链表长度的。可以用双指针（当右指针移动了n个节点时，才生成左节点），左指针落后右指针n个长度。当后面一个指针的next为NULL时，表示到底了，这个时候删除前面一个指针的下一个节点。删除节点需要一个临时节点，用来记录删除节点的后一个节点(方便内存释放，如果不需要释放内存，则不需要临时节点）。
代码实现:
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead -> next = head;
ListNode* right = dummyHead;
ListNode* left = dummyHead;
int count = 0;
while(count < n && right != NULL){
right = right -> next;
count++;
}
right = right -> next;
while(count >= n && right != NULL){
right = right -> next;
left = left -> next;
count++;
}
// left->next = left->next->next; 不释放内存的写法
ListNode* tmp = left -> next;
left->next = tmp->next;
delete tmp;
return dummyHead-> next;
}
};
代码随想录思路：运用双指针，快慢指针。我的思路跟这个一样。不同之处在于我用了一个计数的变量，但是随想录直接用n计数，更加简洁。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
// ListNode *tmp = slow->next; C++释放内存的逻辑
// slow->next = tmp->next;
// delete nth;
return dummyHead->next;
}
};
我刚开始是没有调通的，因为我用来head作为快慢指针的头节点。但是这样，当要删除的就是头节点的时候就很不好操作。使用虚拟头节点的方式，更加高效。
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交**：**
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IIs2Tp7E-1685353234163)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/777bc3bd-2996-4638-992b-10a85191e10f/Untitled.png)]
自己思路：给定两个单链表头节点，那我可以分别遍历两个链表。值相等不等于相交，交叉点的地址是相同的。链表不一定等长和相交。如果两个链表中，当前两个节点地址不等，但是这两个节点的下一个节点地址相等，则下一个节点就是相交点。暴力一点的解法：先遍历一个链表的所有节点并记录其地址。之后用另一个链表的每个节点去比对。
随想录思路：简单来说，就是求两个链表交点节点的指针。要注意，交点不是数值相等，而是指针相等。
求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4QXryNvN-1685353234163)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/8c1662a5-2c35-4575-9dbd-d6c635bf90d6/Untitled.png)]
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
//求链表长度
while(curA !=NULL){
curA = curA-> next;
lenA++;
}
while(curB != NULL){
curB = curB -> next;
lenB++;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if(lenB > lenA){
swap(lenA, lenB);
swap(curA, curB);
}
//求长度差
int gap = lenA -lenB;
while(gap--){
curA = curA->next;
}
//遍历curA和curB，遇到相同值则直接返回
while(curA != NULL){
if(curA == curB){
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
- 时间复杂度：O(n + m)
- 空间复杂度：O(1
这道题，我没有想到先去对齐，这样来简化一下。以后遇见这种长度不一，然后又要匹配中间某一个的题，都可以考虑先将长度对其，再来寻找中间值。
142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-991IVTfC-1685353234164)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/efbecd61-9d24-4ce9-a8ca-501bc2be8ec5/Untitled.png)]
自己思考：没啥好的思路。只想到暴力的，先记录所有已遍历点，遍历下一个点的时候就进行比对。
随想录思路：（牛逼），利用快慢指针来判断是否有环，以及确定有环后点的选取。具体思路：https://programmercarl.com/0142.环形链表II.html#思路
其中涉及到很多数学推理。主要思想是利用速度差来解决。
/**
* 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) {
ListNode* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL){
//两个指针移动的速度快慢不一样，一个1，一个2
slow = slow -> next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
//根据数学推理，从head和快慢指针相遇点到交点距离相等
if(slow == fast){
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return NULL;
}
};
困难及收获
困难
1、有时候有思路，但是在代码细节上容易出现错误。以后多注意边界情况，可以的话画图来进行辅助
2、数学原理容易理解，但是没见过这道题的话，一时半会儿很难想到。多积累吧。
今日收获
链表总结：https://programmercarl.com/链表总结篇.html#链表的理论基础
链表的长度问题，最好找到其共同路段。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述