24. 两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
思路
两两交换节点的重要点在于判断while循环里面的条件，以及cur临时指针应该直向何处？
因此画图理解cur指针的指向以及每一步骤：
拉直后的图像：
由上图知
步骤一：用虚拟头节点连接第二个节点，准备交换
步骤二：1、2两节点进行交换
步骤三：虚拟头节点向后移两位，准备进行下一组交换
cur->next=cur->next->next;//步骤1
cur->next->next=tmp;//步骤2
cur->next->next->next=tmp1;//步骤3
//cur->next既代表着指针域，也代表着下一个节点
代码展示
//给定一个链表，亮亮交换相邻的节点，返回交换后的链表
//不能单纯的改变节点内部的值，而是需要实际的进行节点交换
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
dummyhead = new();//设置一个虚拟头节点
dummyhead = head;//让虚拟的指向head（第0个节点）
cur = dummyhead;//让cur临时指针指向虚拟节点，才能对0，1节点进行操作
while(cur->next != null && cur->next->next != null){
/*思考遍历到什么时候终止？——画图可得：cur指针每次控制后两个指针进行交换（奇数个节点）
同理画图得：偶数时cur-》next的值为空，则结束循环 */
temp = cur->next;//在赋值操作前定义临时temp节点保存cur-》next（第0号节点）
temp1 = cur->next->next->next;//同理要保存节点（第2号节点）
cur->next = cur->next->next;//赋值操作，即虚拟指向第1号节点（头节点为0）
cur->next->next = temp;//第一号节点指向第0号
temp->next = temp1;//第0号指向第2号
//拉直后就是： 虚拟-》1-》0-》2
cur = cur->next->next;//不管交换，只要让cur移动到要交换的两个节点的前一个，即往后移了两位。
}
return dummyhead->next;//返回真正的头节点
}
19.删除链表的的倒数第N个节点
题目链接：19.删除链表的的倒数第N个节点
题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
输入：head = [1], n = 1 输出：[] ：
输入：head = [1,2], n = 1 输出：[1]
思路
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。(还是画图好理解)
第一步：定义fast和slow指针，初始值都为虚拟头节点（dummyhead）
第二步：fast先走n+1步（这里很重要），因为你fast先走了n+1的话，slow最后也应该剩下n+1（从后往前数），那么slow指针实质是落在了倒数第n+1个节点中（方便做删除操作）。
第三步：fast和slow同时移动，直到fast指向末尾（即空null）。
第四步：删除slow指向的下一个节点（即倒数第n个）
代码如下
//删除倒数第n个节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n){
dummyHead = new ListNode(0);//构造虚拟
dummyHead->next = head; // 虚拟指向头节点
fast = dummyhead;
slow = dummyhead; //同时指向虚拟节点
n++;//安全起见，直接加一
while(n && fast != null){//移动快指针，走n步
fast = fast->next;
n--;
//与while(n-- && fast != null)写法一样
}
while(fast != null){
fast = fast->next;
slow = low->next;
//快慢指针一起移动直到fast为空
}
solw->next = slow->next->next;//fast为空时，删除第n个元素（slow-next）的操作
return dummyhead->next;
}
}
面试题 02.07. 链表相交
题目链接：面试题 02.07. 链表相交
题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
输入：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 个节点。
思路
首先要定义两条链表，让cura指针和curb指针分别指向a，b的头结点。在求出两份条链表的长度，求出长度差值，然后让curA移动到和curB末尾对齐的位置。
此时要检查cura和curb是否相同，不同的话，同时向后移动一位，直到遇到有cura==curb，则找到交点，
否则循环退出返回空指针。
代码展示
//链表相交
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
curA = headA;
curB = headB;
int lenA = 0, lenB = 0;//记录a和b链表的长度
while(lenA != 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;//等同于while（gap），gap--；写外面
}
//以下：遍历cura和curb，有相同则直接返回
while(curA != null){
if(curA == curB){
return curA;
}
curA = curA->next;
curB = curB->next;
}
return null;
}
}
总结
链表的种类主要为：单链表，双链表，循环链表
链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
链表是如何进行增删改查的。
数组和链表在不同场景下的性能分析。
链表的虚拟头节点
虚拟头节点的设置是增删改查中十分重要的方法，通过设置虚拟头节点，链表在进行操作时可以不用区分进行头节点和非头节点的操作，使更加方便
表的基本操作
这是练习链表基础操作的非常好的一道题目，考察了：
获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点的数
可以说把这道题目做了，链表基本操作就OK了，再也不用担心链表增删改查整不明白了。
