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，一个2slow = 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#链表的理论基础

链表的长度问题，最好找到其共同路段。