24、两两交换链表中的节点
·模拟节点交换
思路：循环中两两交换
手写模拟一下交换的过程就比较容易了
下图是我写的模拟过程：
代码实现：中规中矩地模拟就完事
时间复杂度O(n)
空间复杂度O(1)
/**
* 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) {
ListNode* cur =head;
ListNode* per =new ListNode();
ListNode* k = new ListNode();
bool t=false;
while(cur!=nullptr&&cur->next!=nullptr){//有可以进行交换的节点
k=cur->next;//per要指向cur->next,先用k存cur->next
cur->next=k->next;//改变cur的指针域
per->next=k;
per=per->next;
per->next=cur;
if(!t){//注意，当头两个节点进行交换后，head也需要进行交换
head=per;
t=true;
}
per=cur;
cur=cur->next;
}
return head;
}
};
收获摘要：carl哥的方法用了虚拟头节点，我没用虚拟头节点，写下来还比较顺畅，就是要注意返回的head因为交换，要改变。
学习的文章链接：https://programmercarl.com/0024.两两交换链表中的节点.html#_24-两两交换链表中的节点
19、删除链表的倒数第N个节点
·链表长度计算，双指针更快
单链表倒着数真是吃饱没事干，正着数再减一减就可以了
题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路：先计算链表的总长度
然后算出正着数是第几个
删除节点
代码实现：
时间复杂度O(n)
空间复杂度O(1)
/**
* 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) {
int m=1;//计数器
ListNode* phead=new ListNode(0,head);//虚拟头节点
ListNode* cur=phead->next;
while(cur->next!=nullptr){//计算链表长度
cur=cur->next;
m++;
}
m=m-n;//从左至右第m个
cur=phead;
while(m>0){
cur=cur->next;
m--;
}
ListNode* d=cur->next;
cur->next=cur->next->next;
delete d;
return phead->next;
}
};
收获摘要：设置虚拟头节点方便处理针对头节点的情况，
比如删掉头节点后，就不能返回头节点，
但是可以返回虚拟头节点的指针域doge
此题用双指针法可以只扫一遍链表，类似于滑块doge
双指针yyds！精简了计算666
ps：双指针的代码可以在文章链接里参考，就不ctrl+v了哈哈哈
复习的时候可以用双指针实现
学习的文章链接：https://programmercarl.com/0019.删除链表的倒数第N个节点.html#_19-删除链表的倒数第n个节点
面试题02.07.链表相交
·世界线收束doge
就是说收束前两条链表不一样长~
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
前提：不存在环
相交点不是数值相等，而是指针(节点)相等
思路：算出两条链表的长度
两条链表相交节点之后的长度相等
进行一个右对齐的操作，然后往后找相交节点
代码实现：
时间复杂度O(n)
空间复杂度O(1)
/**
* 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) {
ListNode* curA=new ListNode(0,headA);
ListNode* curB=new ListNode(0,headB);
int la=0;
int lb=0;
int l;
while(curA->next!=NULL){
curA=curA->next;
la++;
}
curA=headA;
while(curB->next!=NULL){
curB=curB->next;
lb++;
}
curB=headB;
l=(la>lb)?la:lb;
for(int i=1;i<=l;i++){
if(curA==curB){
return curA;
}
else if(la>lb){
curA=curA->next;
la--;
}
else if(la<lb){
curB=curB->next;
lb--;
}
else{
curA=curA->next;
curB=curB->next;
}
}
return NULL;
}
};
收获摘要：虚拟头节点方便考虑头节点的情况（梅开n度），
链表长度不一样就把它拉到一样，然后就一路畅通了。
142、环形链表Ⅱ
·双指针+一些数学运算
他跑、她走，她被追~此处应有bgm：恋爱循环doge
思路：双指针，一快一慢
每次快指针比慢指针还要快一步 (just one)
快指针先进入循环（循环ing）
直到两个指针相遇（！！）
经过一些数学运算
请返回：循环入口
代码实现：
时间复杂度O(n)
空间复杂度O(1)
/**
* 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) {
int xy=0;
ListNode* fast=head;
ListNode* slow=head;
if(head==NULL)return NULL;
while(fast->next!=NULL&&fast->next->next!=NULL){
fast=fast->next->next;
slow=slow->next;
xy++;
if(slow==fast){//两个指针相遇了
slow=head;//一个退回原点，另一个从相遇节点继续循环
while(slow!=fast){
fast=fast->next;
slow=slow->next;
}
return slow;//再相遇就是循环入口节点
}
}
return NULL;
}
};
收获摘要：双指针yyds（这句话我已经说了千百遍~）
理解 x：头节点-循环入口节点
y：循环入口节点-相遇节点
z：相遇节点-循环入口节点
双指针走过的路程以及这三个数之间的关系
还有一点需要注意的是：
当头节点为NULL时，它肯定不能循环，甚至不是个链表，直接返回NULL即可。
学习时长：5h