算法刷题Day4 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

本文主要是介绍算法刷题Day4 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🙋‍♂️ 作者：海码007
📜 专栏：算法专栏
💥 标题：算法刷题Day4 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
❣️ 寄语：书到用时方恨少，事非经过不知难！

0 引言

1 两两交换链表中的节点

🎈 文档讲解：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
🎈 视频讲解：
🎈 做题状态：没看题解就写出来了，比较顺利

1.1 我的解题

这一次还是会涉及到头结点和非头结点处理的差别，所以引入了虚拟头结点统一操作。
这一题涉及到三个指针，cur、pre、tmp。一定要注意cur是从虚拟头结点开始遍历。然后当 cur->next; cur->next->next; cur的后面两个节点都存在时才能进行遍历。可以先看图解的思路

在这里插入图片描述

class Solution {
public:ListNode* swapPairs(ListNode* head) {// 创建虚拟头结点ListNode* dummyNode = new ListNode(-1);dummyNode->next = head;// 创建三个节点指针，主要为了完成交换操作ListNode* cur = dummyNode;ListNode* pre;ListNode* tmp;// 当cur指针、cur的下一个节点指针、以及下下一个指针存在时，才能进行交换// 因为cur第一次指向的是虚拟头结点，后面两个指针才是真正的数据while ( cur && cur->next && cur->next->next){pre = cur->next;tmp = pre->next;    // tmp可以为空指针，不影响// 交换节点cur->next = tmp;pre->next = tmp->next;tmp->next = pre;// 交换完成后，cur指针向后移动两位，因为是两两交换cur = cur->next->next;}return dummyNode->next;}
};

1.2 注意事项

一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序。

2 删除链表的倒数第N个节点

🎈 文档讲解：
🎈 视频讲解：
🎈 做题状态：通过画图，然后写下步骤，做题变轻松很多

2.1 我的代码

具体思路如下：
在这里插入图片描述

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {// 1. 创建虚拟头结点ListNode* dummyNode = new ListNode(0);dummyNode->next = head;// 2. 循环n次，将right指针移动到正确位置ListNode* left = dummyNode;ListNode* right = dummyNode;for (int i = 0; i < n; i++){right = right->next;// 如果倒数第n个节点不存在，则直接返回if (right == nullptr) return dummyNode->next;}// 3. 遍历到最后的空节点while (right->next != nullptr){right = right->next;left = left->next;}std::cout << "right->val = " << right->val;// 4. 删除节点ListNode* tmp = left->next;left->next = tmp->next;delete tmp;return dummyNode->next;}
};

2.2 报错原因分析

但是我在删除目标节点的时候报错了，因为我应该将 left->next = tmp->next; 而不是指向right 节点。

在这里插入图片描述

3 链表相交

🎈 文档讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
🎈 视频讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
🎈 做题状态：没太大问题

3.1 我的解题

需要注意的就是，判断的是节点的地址是否相等，而不是节点内存储的val是否相等

在这里插入图片描述

class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {// 创建虚拟头结点（和前面思路保持一致，习惯使用虚拟头结点）ListNode* dummyA = new ListNode(0);dummyA->next = headA;ListNode* dummyB = new ListNode(0);dummyB->next = headB;// 1.确定最小的长度值int sizeA = 0;int sizeB = 0;ListNode* curA = dummyA->next;while (curA != nullptr){sizeA++;curA = curA->next;}ListNode* curB = dummyB->next;while (curB != nullptr){sizeB++;curB = curB->next;}// 2. 将curA 和 curB 指针对齐// 注意此时需要重新给 curA 和 curB 重置到起始位置curA = dummyA->next;curB = dummyB->next;if (sizeA > sizeB){// 当链表A较长时，需要移动 curA 指针和 curB对齐int dValue = sizeA - sizeB;while (dValue > 0){curA = curA->next;dValue--;}}else if (sizeA < sizeB){// 当链表B较长时，需要移动 curB 指针和 curA 对齐int dValue = sizeB - sizeA;while (dValue > 0){curB = curB->next;dValue--;}}// 3. 开始遍历 curA 和 curB ，看什么时候元素值相等while (curA != nullptr && curA != curB){curA = curA->next;curB = curB->next;}return curA;}
};

4 环形链表II

🎈 文档讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
🎈 视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
🎈 做题状态：有难度

4.1 我的解题

不看题解写不出来，虽然已经想到了快慢指针确定是否有环，但是不知道该如何确定环的入口位置。

有两个关键点：

快慢指针为什么一定会在环内相遇
- 因为判断是否相遇时，不仅移动完快指针后会判断，移动慢指针后也会判断。所以就算快指针跳过慢指针，慢指针移动上去后还是会相遇。
- 下图是代码随想录中的图片，图中的快指针就是刚好跳过慢指针，但是慢指针移动后就相遇了。
如何确定环的入口。
- 根据快慢指针的关系，可以推到出 x = (n - 1) (y + z) + z 公式。
- 然后在快慢指针相遇的时候，再新建一个指针 cur 从头结点位置出发，然后 cur 指针一定会和慢指针在环的入口处相遇。

解题步骤（本题没有头结点特殊情况）：

定义快慢指针，并初始化到头结点位置。
移动快指针移动两次，移动慢指针一次，然后判断是否相等，如果相等则找到相遇点。
找到相遇点后，再新建一个指针 cur ，然后循环遍历知道 cur 指针和 slow 指针相遇，相遇的节点就是环的入口节点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;ListNode* cur = head;// 循环条件是 fast 不为空指针while ( fast!= nullptr ){fast = fast->next;// 由于 fast 要移动两次，所以每移动一次都需要判断是否为空if ( fast != nullptr ){fast = fast->next;slow = slow->next;if (fast == slow) break;}else{return nullptr;}}// 如果 fast 为空说明链表没有环，则返回空if (fast == nullptr) return nullptr;cout << "环的入口节点的值 = " << slow->val;// 新建一个指针从head开始遍历while (cur != slow){cur = cur->next;slow = slow->next;}// cur 和 slow 相遇后退出循环，此时cur的位置就是环的入口节点return cur;}
};