题目引用
- 两两交换链表节点
- 删除链表的倒数第n个节点
- 链表相交
- 环形链表
1.两两交换链表节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
我们先来看一下题目，这题跟昨天的翻转链表比较相似，都是控制节点指针对链表进行修改，这里呢我们先new一个虚拟头结点dummyhead来保证到最后可以找到头结点返回，然后定义一个指针cur在dummyhead位置，tmp在cur->next位置来对其进行修改，tmp1用于标记后面节点避免剩余链表丢失。
接着将cur的next指向tmp的下一个节点
再将这个节点的next指向tmp节点
最后将tmp位置节点next指向tmp1，而cur顺势移动到tmp位置进行下一轮交换。
最后将dummyhead删除，本题就做完啦~
代码：
ListNode* swapPairs(ListNode* head) {
ListNode* dummyhead=new ListNode(-1);
dummyhead->next=head;
ListNode* cur=dummyhead;
while(cur->next!=nullptr&&cur->next->next!=nullptr){
ListNode* tmp=cur->next;
ListNode* tmp1=cur->next->next->next;
cur->next=cur->next->next;
cur->next->next=tmp;
tmp->next=tmp1;
cur=tmp;
}
ListNode* result=dummyhead->next;
delete dummyhead;
return result;
}
2.删除链表的倒数第n个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
首先我们分析一下题目，这道题目是可以通过遍历两遍的方式做出来的，先遍历一遍算出链表长度，再算出差值，删除节点。但是这里亦可以用快慢指针来做，并且只需要一次遍历。
首先new一个虚拟头结点dummyhead，再定义fast和slow指针都指向dummyhead。再我们让fast先移动n+1个节点，再fast和slow节点同时移动，直到fast为空。然后删除slow后面的节点返回链表。
为什么是n+1个节点，为什么同时移动呢？
首先回答为什么先让fast先走再同时移动，因为当fast和slow同时移动时，fast和slow保持了相对距离n+1，当fast移动到链表结束位置时，slow与其刚好相差n+1个节点，也就实现了一次遍历找到倒数第n个节点的期望。
那么为什么是n+1呢？因为当我们找到刚好是倒数第n个位置的节点时，我们对其进行移除操作是很困难的，所以找到倒数第n+1个刚刚好可以将第n个轻易的删除掉。
附上代码：
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head->next==nullptr) return nullptr;
ListNode* dummyhead=new ListNode(0);
dummyhead->next=head;
ListNode* fast=dummyhead;
ListNode* slow=dummyhead;
while(n>=0){
fast=fast->next;
n--;
}
while(fast!=nullptr){
fast=fast->next;
slow=slow->next;
}
ListNode* tmp=slow->next;
slow->next=slow->next->next;
delete tmp;
return dummyhead->next;
}
3.链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
这道题很简单，我们先通过两次遍历得到两个链表的长度，然后算出长度差，让长的链表的指针先走长度差gap步，接着两个指针同时移动一一比对，相等即返回。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA=0,lenB=0;
ListNode* curA=headA;
ListNode* curB=headB;
while(curA){
curA=curA->next;
lenA++;
}
while(curB){
curB=curB->next;
lenB++;
}
curA=headA;curB=headB;
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
while(curA){
if(curA==curB){
return curA;
}
curA=curA->next;
curB=curB->next;
}
return NULL;
}
4.环形链表II
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
首先，我们需要判断一下是否是环形链表，定义一个fast和一个slow，fast每次走两步，slow每次走一步，如果有环，那么fast和slow一定会在环内的某个位置碰上，因为fast和slow有速度差。
那么怎么找到环形链表的开头呢？
这就牵扯到数学问题，设头到环的入口的长度为x，入口到fast与slow相遇的位置的长度为y，环剩下的长度为z，那么不难得出
2*(x+y)=n*(y+z)+x+y
x+y=n*(y+z)
x=n*(y+z)-y
x=(n-1)(y+z)+z
那么就说明了从头结点出发一个指针，fast出发一个指针，他们相遇的位置就是环形链表的入口。
那么代码如下：
ListNode *detectCycle(ListNode *head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
ListNode* i1=head;
ListNode* i2=fast;
while(i1!=i2){
i1=i1->next;
i2=i2->next;
}
return i1;
}
}
return NULL;
}
总结
今天的题目都比较考验画图和发现规律的能力，沉下心好好学习，慢慢寻找总能找到规律。
