代码随想录一刷记录Day4——leetcode24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II
前言
之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！
leetcode24. 两两交换链表中的节点
题目链接leetcode24. 两两交换链表中的节点
思路
代码
classSolution{public:ListNode*swapPairs(ListNode*head){ListNode*dummyhead=newListNode(0);dummyhead->next=head;ListNode*cur=dummyhead;while(cur->next!=nullptr&&cur->next->next!=nullptr){ListNode*tmp=cur->next;ListNode*tmp1=cur->next->next->next;//交换（3步）cur->next=cur->next->next;cur->next->next=tmp;cur->next->next->next=tmp1;//更新cur的位置cur=cur->next->next;}ListNode*newhead=dummyhead->next;deletedummyhead;returnnewhead;}};leetcode19.删除链表的倒数第N个节点
题目链接leetcode19.删除链表的倒数第N个节点
思路
本题主要是双指针（快慢指针）的用法。
1、要想删除倒数第N个节点，那么就要让当前遍历的指针停在要删除节点的前一个节点位置
2、利用快慢指针，快指针先走N+1步，然后让快慢指针同时向前走，当快指针走完链表，即指向null的时候，此时慢指针刚好停留在要删除节点的前一个节点位置。
3、配合虚拟头节点的使用，方便处理删除头结点的逻辑
代码
classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){//虚拟头节点，统一处理删除头节点的情况ListNode*dummyhead=newListNode(0);dummyhead->next=head;ListNode*fast=dummyhead;ListNode*slow=dummyhead;//1、fast先走n+1步for(inti=0;i<=n;i++){fast=fast->next;}//2、fast和slow同时走，直到fast为空while(fast!=nullptr){fast=fast->next;slow=slow->next;}//3、此时slow指向倒数第n个节点的前驱节点ListNode*tmp=slow->next;//要删除的节点slow->next=slow->next->next;//跳过要删除的节点deletetmp;//4、返回新的头节点ListNode*newhead=dummyhead->next;deletedummyhead;returnnewhead;}};leetcode面试题 02.07. 链表相交
题目链接面试题 02.07. 链表相交
思路
本题依然是双指针的思想，基于双指针有以下两种思路：
思路1：
分别计算两个链表的长度，并求出两个链表长度的差值，然后让代表长链表的指针移动到和短链表末尾对齐的位置，然后判断两个指针是否相等，如果不相等，则同时向后移动两个指针，若遇到curA == curB，则找到交点，否则循环退出返回空指针。
思路2：
构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB；指针 B 先遍历完链表 headB ，再开始遍历链表 headA。若两链表有 公共尾部指针 A , B 会同时指向第一个公共节点，若两链表 无 公共尾部指针 A , B 会同时指向 null 。
代码
//方法一classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){ListNode*curA=headA;ListNode*curB=headB;intlenA=0;intlenB=0;while(curA!=nullptr){// 求链表A的长度lenA++;curA=curA->next;}while(curB!=nullptr){lenB++;curB=curB->next;}curA=headA;curB=headB;// 让curA为最长链表的头，lenA为其长度if(lenB>lenA){swap(lenA,lenB);swap(curA,curB);}// 求长度差intgap=lenA-lenB;// 让curA和curB在同一起点上（末尾位置对齐）while(gap--){curA=curA->next;}// 遍历curA 和 curB，遇到相同则直接返回while(curA!=NULL){if(curA==curB){returncurA;}curA=curA->next;curB=curB->next;}returnNULL;}};//方法二classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){if(headA==nullptr||headB==nullptr){returnnullptr;}ListNode*pA=headA;ListNode*pB=headB;//当pA == pB时，要么找到相交点，要么同时为NULL（不相交）while(pA!=pB){//pA走一步，如果到末尾则转到pBpA=(pA!=nullptr)?pA->next:headB;//pB走一步，如果到末尾则转到pApB=(pB!=nullptr)?pB->next:headA;}returnpA;}};*/leetcode142.环形链表II
题目链接leetcode142.环形链表II
思路
本题依然是双指针（快慢指针）的用法。
解题分为两步，第一步先判断链表是否有环，第二步找到环的入口。
1、判断是否有环：首先让快慢指针都指向头节点，然后快指针一次走两步，慢指针一次走一步，若相遇说明有环。
2、找环：让快指针回到头节点，然后slow 和 fast 同时每轮向前走 1 步；若重合，则找到表环入口，返回 slow 指向的节点即可。
(原理还需搞懂)
代码
classSolution{public:ListNode*detectCycle(ListNode*head){//阶段一：判断是否有环，找到相遇点ListNode*fast=head;ListNode*slow=head;boolhasCycle=false;while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;//慢指针走一步fast=fast->next->next;//快指针走两步if(slow==fast){//相遇 有环hasCycle=true;break;}}//如果没有环，返回nullptrif(!hasCycle){returnnullptr;}//阶段二：找到环的入口//将slow重置到头节点，fast保持在相遇点slow=head;while(slow!=fast){slow=slow->next;//各走一步fast=fast->next;}returnslow;//入口节点}};