第四天|24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II
24. 两两交换链表中的节点
帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili
24. 两两交换链表中的节点 - 力扣（LeetCode）
笔记
当前操作的是cur->next和cur->next->next这两个元素的更换。为什么这样做：因为调换时候会涉及到前一个元素，如果使用cur为当前遍历的值，会出现无法找到前一个节点的情况。
注意循环条件while(cur->next!=nullptr&&cur->next->next!=nullptr)：
1.同时要cur->next!=nullptr和cur->next->next!=nullptr，前者是奇数情况，后者是偶数情况；
2.cur->next!=nullptr要在cur->next->next!=nullptr之前，因为如果cur->next==nullptr，会导致cur->next->next!=nullptr这一判断语句非法操作
具体操作流程画图即可
实操出现问题
没有把dummyhead 指向原链表head。
代码/比较
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyhead=new ListNode(0);//虚拟头节点ListNode* cur=dummyhead;//现在遍历的是cur->next和cur->next->nextdummyhead->next=head;while(cur->next!=nullptr&&cur->next->next!=nullptr){ListNode* temp=cur->next;ListNode* temp1=cur->next->next->next;cur->next=cur->next->next;temp->next->next=temp;temp->next=temp1;cur=temp;}return dummyhead->next;}
};
19.删除链表的倒数第N个节点
19.删除链表的倒数第N个节点 | 代码随想录
链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili
笔记：
设计删除的链表操作一定要处理的是cur->next。
fast要提前出发n+1次。
实操出现问题：
delete时候直接删除了链表内部元素，注意用tmp
代码/比较：
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyhead=new ListNode(0);//虚拟头节点dummyhead->next=head;//ListNode* fast=dummyhead;ListNode* slow=dummyhead;//注意：结束时应该指向被删除的节点之前n++;while(n--&&fast!=nullptr){fast=fast->next;}while(fast!=nullptr)//双指针同时向后移动，让slow结束时指向被删除节点之前{fast=fast->next;slow=slow->next;}//删除slow->nextListNode* tmp=slow->next;slow->next=slow->next->next;delete tmp;return dummyhead->next;}
};
面试题 02.07. 链表相交
笔记
面试题 02.07. 链表相交 | 代码随想录
为什么要先找到差值？让两个链表处于同一个起点？：因为处于同一个起点后，两个链表后面的位置应该是一摸一样的
步骤如下：
1.找到两个链表各自的长度
2.让长的那个链表cura往前移动,保持到和短的那个链表相同的长度
3.遍历,知道两个指针相等,如果最后都没有相等,则没有相交
实操出现的问题
思路清晰没啥问题
代码/对比
我自己的:
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//获取两个链表的长度 int lenA=0;int lenB=0;ListNode* cura=headA;ListNode* curb=headB;while(cura!=NULL){cura=cura->next;lenA++;}cura=headA;while(curb!=NULL){curb=curb->next;lenB++;}curb=headB;//找到更大的那个长度if(lenA>lenB)//A更长{//让A的cura往前跑int sub=lenA-lenB;while(sub--){cura=cura->next;}//对比指针即可while(cura!=NULL&&curb!=NULL){if(cura==curb){return cura;}cura=cura->next;curb=curb->next;}return NULL;}else//B更长{//让B的curb往前跑int sub=lenB-lenA;while(sub--){curb=curb->next;}//对比指针即可while(cura!=NULL&&curb!=NULL){if(cura==curb){return cura;}cura=cura->next;curb=curb->next;}return NULL;}}
};
太蠢了,可以直接交换两个链表的关键信息保持A链表的长度最长
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;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) {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;}
};
142.环形链表II
142.环形链表II | 代码随想录
把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili
笔记:
1.怎么判断有没有环:
快慢指针,一个走两步一个走一步.为什么不用担心快指针跳过慢指针:因为快指针相对于慢指针就是一步一步在前进,一定不会错过
2.怎么找到环开始的点?
为什么慢指针一定在第一圈和快指针相遇:展开画图可知慢指针走那一圈快指针一定走到他前面去;
通过公式推导知:两个指针分别从相遇点和head出发一定在环的起点相遇(无论那个从相遇点在环里走了多少圈)
实操出现的问题:
再把逻辑分析清楚
代码/对比:
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast=head;ListNode* slow=head;//判断是否有环while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow)//如果相遇了{ListNode* index1=head;ListNode* index2=fast;while(index1!=index2){index1=index1->next;index2=index2->next;}return index1;}}return NULL;}
};