代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07. 链表相交、142.环形链表II

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

24. 两两交换链表中的节点

题目链接：24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

文章讲解/视频讲解：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

思路

这道题比较绕，需要自己在纸上画一下。

可以采用迭代法来处理，每次迭代以两个节点为单位，这两个节点一前一后分别为pre和curr。另外需要提前获取pre的前一个节点pre_head。在每次迭代过程中，首先存一下curr->next（因为接下来会截断）为tmp，然后将curr指向pre，pre指向tmp，pre_head指向curr。之后进行pre_head、pre、curr的迭代，注意检查节点是否为空。

示意图如下：

C++实现

/*** 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) {if(head == nullptr || head->next == nullptr) return head;ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* pre_head = dummyHead, *pre = head, *curr = head->next;while(curr != nullptr){ListNode* tmp = curr->next;curr->next = pre;pre->next = tmp;pre_head->next = curr;pre_head = pre;pre = tmp;if(pre == nullptr) break;curr = pre->next;}return dummyHead->next;}
};

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

题目链接：19.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

文章讲解/视频讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

思路

最简单直接的想法：遍历获得链表的长度，然后再遍历一遍，找到要删除节点的前一个节点，删除该节点。这样需要两趟。

一趟解决的方法没有想出来，看了卡哥的教程，发现可以用双指针来解决。

指定一个慢指针slow和一个快指针fast，让slow指向正向第一个节点，fast指向正向第n + 1个节点。

当fast遍历到链表最后一个节点时，slow正好指向链表倒数第n + 1个节点，此时删除slow之后的节点即可。

C++实现

/*** 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* slow = dummyHead, *fast = dummyHead;int i = 1;while(i < n + 1){fast = fast->next;i++;if(fast == nullptr) return dummyHead->next;}while(fast->next != nullptr){slow = slow->next;fast = fast->next;}ListNode* tmp = slow->next;slow->next = slow->next->next;delete tmp;return dummyHead->next;}
};

面试题 02.07. 链表相交

题目链接：面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

文章讲解/视频讲解：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

思路

设置两个指针ptrA、ptrB，分别指向头节点headA和头节点headB。令ptrA、ptrB同时开始迭代，当ptrA指向链表尾部时，掉头指向headB，当ptrB指向链表尾部时，掉头指向headA，ptrA与ptrB相等时，即为两个链表的交点。如果ptrA、ptrB同时等于nullptr，则说明遍历完了两轮，始终没有相等，两个链表没有交点。

C++实现

/*** 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) {if(headA == nullptr || headB == nullptr) return nullptr;ListNode* ptrA = headA, *ptrB = headB;while(ptrA != nullptr || ptrB != nullptr){if(ptrA == nullptr) ptrA = headB;if(ptrB == nullptr) ptrB = headA;if(ptrA == ptrB) return ptrA;ptrA = ptrA->next;ptrB = ptrB->next;}return nullptr;}
};

142.环形链表II

题目链接：142.环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

思路

这道题目首先一个思路是用哈希表。用一个指针来遍历该链表，一边遍历一边把扫过的节点存到哈希表里，如果发现遍历的节点之前在哈希表里存储过，该节点便是链表入环的第一个节点，如果指针最终指向nullptr，则说明无环。

还有一种思路是采用快慢指针，这种思路我之前学习过，再遇到时回想了起来。首先定义一个慢指针slow和快指针fast，慢指针每次+1，快指针每次+2。如果快指针最终指向nullptr，则说明无环，如果快指针追上慢指针，与慢指针相等，则说明有环。这时有一个定量的计算，如下图，设无环的阶段长度为a，有环的阶段中，从入环第一个节点到快慢指针相遇的位置长度为b，环中剩余的长度为c。

快指针走过的长度为慢指针走过长度的二倍，快指针走过的长度为a + b + c + b，慢指针走过的长度为a + b，于是有a + b + c + b = 2 * (a + b)，化简得c = a。这时候就明了了，slow指针如果在环中继续迭代的话，再次迭代到入环节点的距离正好和从头节点到入环节点的距离相等。

只要再设置一个指针tmp指向头节点，让tmp指针和slow指针同时遍历，当tmp指针和slow指针相等时，正好是入环节点处。

C++实现

/*** 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) {if(head == nullptr || head->next == nullptr) return nullptr;ListNode* slow = head, *fast = head, *tmp = head;do{slow = slow->next;fast = fast->next->next;}while(fast != nullptr && fast->next != nullptr && slow != fast);if(fast == nullptr || fast->next == nullptr) return nullptr;while(tmp != slow){tmp = tmp->next;slow = slow->next;}return slow;}
};

这篇关于代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07. 链表相交、142.环形链表II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---