24.两两交换链表中的节点
题目：24. 两两交换链表中的节点 - 力扣（LeetCode）
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
图解思路
首先，虚拟头结点挺方便链表进行增删改操作的。本题操作用到三个指针，cur指针指向虚拟头结点，因为要交换的是第一第二个节点，往后的操作都是cur要指向交换节点的前一个节点。
步骤一cur先指向要交换的第二个节点，然后特别说明要实现步骤二，就得事先用临时指针1储存第一个节点的地址（考虑到单向链表的特性），同理， 临时指针2要保留第二个节点的下一个节点的地址（因为步骤二完成时就失去了和下一个节点的连接）。最后释放虚拟头结点就行。
代码
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode*dummyhead=new ListNode(0);
dummyhead->next=head;
ListNode*cur=dummyhead;
while(cur->next!=NULL&&cur->next->next!=NULL)
{
ListNode*tmp=cur->next;
ListNode*tmp1=cur->next->next->next;//记录要交换的第一个节点和第二个节点的下一个
//两两交换过程
cur->next=cur->next->next;
cur->next->next=tmp;
cur->next->next->next=tmp1;
//更新cur的指向，就是下一个两两交换元素的前一位
cur=cur->next->next;
}
ListNode*result=dummyhead->next;
delete dummyhead;
return result;
}
};最后返回头结点时，注意先保存dummyhead->next的值不然释放dummyhead的时候找不到头结点的位置。
19.删除链表的倒数第n个结点
题目：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路，快慢指针法+虚拟头结点。
找到倒n个节点的关键就是快指针比慢指针先走多少步。但是，快指针要快n+1步是要让慢指针指向被删节点的前一个节点。
模拟一遍走法就比较好理解了。复习到一个点就是要删除哪个节点就让指针指向该节点的前一个节点，然后同步移动直到快指针指向null。特别留意c++中还有手动释放节点。
代码
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode*dummyhead=new ListNode(0);
dummyhead->next=head;
ListNode*fast=dummyhead;
ListNode*slow=dummyhead;
n++;//+1是因为要指向被删节点的前一个
while(n--&&fast!=NULL)//快指针快n步
{
fast=fast->next;
}
while(fast!=NULL)//快慢指针同步移动
{
fast=fast->next;
slow=slow->next;
}
ListNode*tmp=slow->next;//删除，手动释放
slow->next=tmp->next;
delete tmp;
return dummyhead->next;
}
};图示理解
面试题：链表相交
题目：面试题 02.07. 链表相交 - 力扣（LeetCode）
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
数学方法思路：（参考题解）
构建两个指针A和B，分别指向两个链表的表头，A先遍历headA，在遍历headB，直到达到首个公共节点node，共走步数b+（a-c)。同理，B先遍历headB，在headA，达到node时停下，共走步数a+(b-c)。----其实就是让两个指针分别走一遍相交链表的所有节点，只是出发点不一样。
如下式所示，此时指针 A , B 重合，并有两种情况：
a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。
因此返回 A 即可。
代码也比较简洁：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A = headA, *B = headB;
while (A != B) {
A = A != nullptr ? A->next : headB;
B = B != nullptr ? B->next : headA;
}
return A;
}
};
快慢指针
本题注意一个非常易错难以理解的点，就是求节点相交的指针，交点不是数值相等而是指针相等。如图
A,B链表在节点8相交之前都有一个相同值的节点，但它们不是相交的起始节点。我想，这是因为起始节点是从尾端开始数起的。
所以本题的思路是，
1.定义两个指针，分别指向两个链表的头结点
2.分别遍历链表，求出各自的长度
3.求两个链表的长度差，定A为较长的链表，并且指针cura比curb先走长度差个节点。（使两链表尾端齐平）
4.然后同时遍历直到指针相同，即找到相交节点，返回交点，否则返回空
代码
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode*curA=headA;
ListNode*curB=headB;
//获取链表长度
int lenA=0,lenB=0;
while(curA!=NULL)
{
curA=curA->next;
lenA++;
}
while(curB!=NULL)
{
curB=curB->next;
lenB++;
}
//易错点：遍历完之后两个指针没有重新指向表头
curA=headA;
curB=headB;
if(lenA<lenB)
{
swap(lenA,lenB);
swap(curA,curB);
}
//较长的链表多走n步
int n=lenA-lenB;
while(n--)
{
curA=curA->next;
}
while(curA!=NULL)
{
if(curA==curB)return curA;//如果指针相同，证明找到相交节点
curA=curA->next;
curB=curB->next;
}
return NULL;
}
};142.环形链表Ⅱ
题目：142. 环形链表 II - 力扣（LeetCode）
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路
定义一个快慢指针，快指针总是比慢指针快一步，如果快指针遇到空指针，那么环不存在，如果遇到慢指针，环就存在。且，在环中时，快指针每走一步，就与慢指针更接近一步，而且，当它们相遇时，快指针至少比慢指针多走了一圈
如何找到入口，且看公式 快指针走了x+y+n(z+y),慢指针走了x+y,由于快指针比慢指针多走一步，所以有等式方程
x+y+n(z+y)=x+y
化简移动： x=n(z+y)-y
提取一个z+y出来就是 x=(n-1)(z+y)+z（n>=1)
当n等于1时，快指针在环里转一圈就遇到了慢指针
同时，n=1时x等于z，那我们就可以安排两个指针，一个从头结点出发，一个从相遇节点出发，都同时移动一步，它们相遇的节点就是环的入口。
n>1时说明快指针要在环里转n圈才能遇到慢指针，区别就是要找到入口节点时，从相遇节点出发的指针要在环里转（n-1）圈才能遇到从头结点出发的指针。
模拟图
转载于：https://www.yuque.com/xiaoshan_wgo/alog/pcenhscg4tmx6ogz
动图：
想象一下操场跑步。
代码
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=fast;//从相遇节点出发
ListNode*index2=head;//从头结点出发
while(index1!=index2)//找环的入口
{
index1=index1->next;
index2=index2->next;
}
return index1;
}
}
//如果没找到环就返回空
return NULL;
}
};今天就是快慢指针的加强使用，感觉自己运用得越来越熟练了，这就是参加训练营的意义吧，这几天做的题换做以前三天打鱼两天晒网的我得做两星期。
链表专题总结图：