C++刷题笔记(7)——leetcode24、19、142、面试题02.07

本文主要是介绍C++刷题笔记(7)——leetcode24、19、142、面试题02.07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1：24.两两交换链表中的节点

在这里插入图片描述

解法一：迭代法

解题思路：
在这里插入图片描述
用cur表示当前到达的节点，每次需要交换cur后面的两个节点

当cur后面没有节点或者只有一个节点，则没有更多的节点需要交换，此时结束交换。否则，获得cur后面的两个节点temp和temp1，通过更新节点的指针关系实现两两交换节点。

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);      // 设置一个虚拟头结点dummyHead->next = head;                     // 将虚拟头结点指向headListNode* cur = dummyHead;                  // 定义一个新的指针，指向虚拟头节点while (cur->next != nullptr && cur->next->next != nullptr) {   //指针的下一个节点和下下个节点都不为空ListNode* tmp = cur->next;              // 记录临时节点   相当于保存示例中的1ListNode* tmp1 = cur->next->next->next; // 记录临时节点   相当于保存实例中的3cur->next = cur->next->next;            // 步骤一cur->next->next = tmp;                  // 步骤二cur->next->next->next = tmp1;           // 步骤三cur = cur->next->next;                  // cur移动两位，准备下一轮交换}return dummyHead->next;}
};

解法二：递归法

先空着

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

在这里插入图片描述

解法一：暴力解法

遍历链表得到其长度L，然后再对链表进行遍历操作，当遍历到L-n+1时就是要删除的节点

class Solution {
public:int getLength(ListNode* head) {       //获取链表长度，链表从长度从1开始计算int length = 0;while (head) {length++;head = head->next;}return length;}ListNode* removeNthFromEnd(ListNode* head, int n) {     ListNode* dummy = new ListNode(0, head);       //定义虚拟头节点int length = getLength(head);ListNode* cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur->next;}cur->next = cur->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};

解法二：双指针法

定义fast指针和slow指针，初始值为虚拟头节点
在这里插入图片描述

需要找到倒数第n个节点的前一个节点，如果fast比slow超前n+1个节点，那么当fast遍历到链表的末尾时，slow就恰好处于倒数第n个节点。

为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
在这里插入图片描述

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {     ListNode* dummyHead = new ListNode(0, head);       //定义虚拟头节点dummyHead->next = head;ListNode* fast = dummyHead;ListNode* slow = dummyHead;while (n-- && fast != NULL) {            //fast先走n步fast = fast->next;}fast = fast->next;                       //fast再走一步，因为需要让slow指向删除节点的上一个节点while (fast != NULL) {                   //fast和slow一块移动，直到fast移动到NULLfast = fast->next;slow = slow->next;}slow->next = slow->next->next;delete dummyHead->next;}
};

题目3：142.环形链表Ⅱ

在这里插入图片描述

解法：双指针法

解题思路：
首先要判断链表中是否有环；
如果有环，需要找到环的入口

判断链表中是否有环：
定义fast和slow两个指针，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。(如果有环就一定会相遇且在环中相遇)
在这里插入图片描述
如果有环，找到环的入口：
假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：

在相遇时，slow指针走过的节点数为：x + y，fast指针走过的节点数为：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，(y+z)为一圈内节点的个数。

fast指针每次移动两个节点，slow指针每次移动一个节点，因此x + y = x + y + n (y + z)，化简后再提一个(y + z)可得x = ( n - 1)( y + z) + z，即从链表头部到入环点的距离，等于从相遇点到入环点的距离加上(n-1)圈的环长。

因此就可以在相遇节点定义一个指针index1，在头节点定义一个指针index2，让index1和index2同时移动，每次移动一个节点，它们相遇的地方就是环形入口的节点。
在这里插入图片描述
在代码随想录中还有更多细节解释，但是只要弄懂原理细节部分也都不难

在官方题解中，当fast和slow相遇时，定义了一个指针pre指向头节点，找pre和slow在环中的相遇处，原理也是同这种做法一样。

class Solution {
public:ListNode* detectCycle(ListNode* head) {ListNode* fast = head;                           //定义快慢指针ListNode* slow = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;                           //慢指针每次移动一个节点fast = fast->next->next;                     //快指针每次移动二个节点if (slow == fast) {                          //快慢指针相遇ListNode* index1 = fast;                 //在相遇节点处定义index1ListNode* index2 = head;                 //在头节点处定义index2while (index1 != index2) {               //从相遇点和头节点处开始查找直至相遇index1 = index1->next;index2 = index2->next;}return index2;                           //index1和index2相遇处就是环形的入口节点}}return NULL;}
};

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

在这里插入图片描述

解法一：哈希集合

占位

解法二：双指针法

解题思路一：
代码随想录的解题思路是为两个链表分别定义两个指针，用这两个指针求两个链表的长度和长度的差值，然后将长的链表的指针移动到和短的链表末尾对齐的位置，最后遍历后面的链表比较两个指针是否相同
在这里插入图片描述

class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {ListNode* curA = headA;              //定义链表A的指针，指向头节点ListNode* curB = headB;              //定义链表B的指针，指向头节点int lenA = 0, lenB = 0;while (curA != NULL) {               //求链表A的长度lenA++;curA = curA->next;}while (curB != NULL) {               //求链表B的长度lenB++;curB = curB->next;}curA = headA;                        //指针重新指向头节点curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {          //这一步是为了确保链表A始终为较长的那个swap(lenA, lenB);swap(curA, curB);}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（相当于末尾位置对齐）while (gap--) {curA = curA->next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != NULL) {if (curA == curB) {return curA;}curA = curA->next; curB = curB->next;}return NULL;}
};

代码随想录的解法比较清晰，但是官方的实现更妙
解题思路二：
首先为两个链表headA和headB分别创建两个指针pA和pB，指向其头节点，两个指针依次遍历两个链表，如果指针pA为空，则将指针pA移到链表headB的头节点；如果指针pB为空，则将指针pB移到链表headA 的头节点，当指针pA和pB指向同一个节点或者都为空时，返回它们指向的节点或者null。
在这里插入图片描述

class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {if (headA == nullptr || headB == nullptr) {           //有链表为空，则一定不相交return nullptr;}ListNode* pA = headA, * pB = headB;                   //分别定义链表的指针，指向头节点while (pA != pB) {                                    //遍历链表pA = pA == nullptr ? headB : pA->next;            //如果指针pA不为空，则将指针pA移到下一个节点；如果指针pA为空，则将指针pA移到链表headB的头节点；pB = pB == nullptr ? headA : pB->next;            //最后两个指针相遇时就是相交的地方}return pA;}
};