二刷代码随想录训练营Day 4|24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交 、142.环形链表II、总结
1.两两交换链表中的结点
题目链接/文章讲解/视频讲解： 代码随想录
代码：
/**
* 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* dummyhead = new ListNode(0);
dummyhead->next = head;
// 交换cur之后的两个结点
ListNode* cur = dummyhead;
while(cur->next != NULL && cur->next->next != NULL){
ListNode* temp = cur->next;
ListNode* temp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp;
temp->next = temp1;
cur = cur->next->next;
}
return dummyhead->next;
}
};note：卡住了！！！
这一次我的思路就有问题，本来是3步才能实现的交换，我只想到两步。同时我也没有意识到，在这里交换cur后的两个结点比较方便，而且这样cur不会受到波及，也可以从dummyhead开始遍历了。
具体的思路就是利用cur来遍历整个链表，同时交换cur后的两个结点，在交换过程中我们需要去在这之前保存两个结点cur->next 和 cur->next->next->next。以及，交换完成后，cur每次向后移动两个结点。
2.删除链表的倒数第N个结点
题目链接/文章讲解/视频讲解：代码随想录
代码：
/**
* 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) {
// 题上已经说明了 n 是合法的，不会超过链表的长度
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* fast = head;
ListNode* slow = dummyhead; // slow是要删除结点的前一个结点,因此和fast的距离是n+1，从dummyhead开始
while(n--){
fast = fast->next;
}
while(fast != NULL){
fast = fast->next;
slow = slow->next;
}
ListNode* temp = slow->next;
slow->next = slow->next->next;
delete temp;
return dummyhead->next;
}
};思路：这次成功做出来了。
其实就是利用两个指针的相对距离来确定倒数第n个结点的前一个结点的位置。为了找到被删除结点的前一个结点，让fast从head出发，而让slow从dummyhead出发。
边界的处理，我通过画图模拟得出，fast最后指向空的时候，slow才到达要删除结点的前一个结点，因此while循环的条件是fast！=NULL。
3.链表相交
题目链接/文章讲解：代码随想录
代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int m = 0; // A链表的长度
int n = 0; // B链表的长度
// 计算两个链表的长度
ListNode* curA = headA;
while(curA){
m++;
curA = curA->next;
}
ListNode* curB = headB;
while(curB){
n++;
curB = curB->next;
}
// 找到合适的出发位置
curA = headA;
curB = headB;
int index;
if(m > n){
index = m - n;
while(index--){
curA = curA->next;
}
}else{
index = n - m;
while(index--){
curB = curB->next;
}
}
// 开始检测
while(curA != NULL){
if(curA == curB){
return curA;
}
curA = curA->next;
curB = curB->next;
}
return nullptr;
}
};note：首先一个易错点就是结点的数值相等，结点不一定是两个链表的公共结点。我们在比较的时候要去比较指针才对。
为了能够让两个遍历链表的指针可以从后端对其，我们要计算出两个链表的长度。然后根据链表的长度差，来找到两个链表遍历的正确的起点。
接着就是同时遍历两个链表，然后去比较指针，找出第一个公共节点了。
4.环形链表
题目链接/文章讲解/视频讲解：代码随想录
代码：
/**
* 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* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
// 如果有环，则fast和slow一定会相遇
if(slow == fast){
// 环的入口 = 此时从head 和 相遇点 出发的指针的相遇点
ListNode* index1 = head;
ListNode* index2 = slow;
while(index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return nullptr;
}
};note：
有数学公式计算可知 图中的 x = z
如何判断有没有环：设置快慢指针，快指针每次移动2个结点，慢指针每次移动1个结点，如果两个指针相遇，说明有环。
为何有环就一定会相遇：因为在有环的情况下，相对于慢指针，快指针相对于它是以相对速度每次一个结点一个结点地移动的。因此两者不会错开。
怎么判断入口点：因为x=y。环的入口 = 此时从head 和 相遇点 出发的指针的相遇点。
5.总结
原文地址：https://blog.csdn.net/weixin_64434454/article/details/140572089
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！