本文主要是介绍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;}
};
这篇关于C++刷题笔记(7)——leetcode24、19、142、面试题02.07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
