24. 两两交换链表中的节点
题目：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
解题思路：
这道题还是使用虚拟头结点来解决，这道题的交换节点的方式分为三步。
- 用第一个元素（从虚拟头节点开始）连接到第三个元素
- 用原第三个元素连接第二个元素
- 用原第二个元素连接第四个元素
这样就得考虑第二个元素、第四个元素都会在连接的过程中被丢失掉所以需要提前记录。完成这些步骤后继续把当前的指针向下移动两格。
需要注意的是，对于链表元素为奇数时cur.next.next为空就说明循环结束了，为偶数时cur.next为空就说明循环结束了，顺序上需要先写cur.next避免空指针。
var swapPairs = function (head) {
let dummyHead = new ListNode(0, head);
let cur = dummyHead;
while (cur.next !== null && cur.next.next !== null) {
let temp1 = cur.next;
let temp2 = cur.next.next.next;
cur.next = cur.next.next;
cur.next.next = temp1;
temp1.next = temp2;
cur = cur.next.next;
}
return dummyHead.next;
};
19.删除链表的倒数第N个节点
题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解题思路：
定义快慢指针，慢指针指向虚拟头结点，快指针向后移动n步。完成之后把快慢指针依次向后移动，循环终止的条件是fast.next === null，这个时候slow指针指向了待删除节点的前一个节点，进行删除操作即可。
var removeNthFromEnd = function (head, n) {
let dummyHead = new ListNode(0, head);
let slow = dummyHead;
let fast = dummyHead;
while (n) {
fast = fast.next;
n--;
}
while(fast.next !== null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyHead.next
};
160.相交链表
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。
换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
解题思路：
这道题首先需要把长链表里的指针和短链表对齐，相当于对应链表内的cur指针同时向后遍历会同时到达终点。然后依次向后遍历，如果遇到节点相等就说明找到了相交节点。这里需要注意长链表一开始是不能确定的，所以中间用交换操作保证curA始终对应的是长链表。
const getLen = (head) => {
let len = 0;
cur = head;
while (cur) {
len++;
cur = cur.next;
}
return len;
}
var getIntersectionNode = function (headA, headB) {
let curA = headA;
let curB = headB;
let lenA = getLen(headA);
let lenB = getLen(headB);
if (lenB > lenA) {
[lenA, lenB] = [lenB, lenA];
[curA, curB] = [curB, curA];
}
let gap = lenA - lenB;
while (gap) {
curA = curA.next;
gap--;
}
while (curA !== null) {
if (curA === curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
};
142.环形链表II
题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路：
设置快慢指针，快指针一次走两步，慢指针一次走一步，如果有环两个指针一定一定会相遇，因为快指针每次比慢指针走的快一步，所以可以追上。注意循环结束的条件有两个 fast !== null && fast.next !== null，因为fast一次走两步，不判断就走空了。
相遇后，设置两个节点，一个从头结点开始走，一个从相遇点向前走，这次相遇后就是环的入口。这里的原因在于快指针至少要多走一圈才能相遇slow指针，此时，一圈中剩下的部分到入口和从头开始到入口，两段距离就是相同的。
var detectCycle = function(head) {
let slow = head;
let fast = head;
while(fast !== null && fast.next !== null){
slow = slow.next;
fast = fast.next.next;
if(slow === fast){
let index1 = head;
let index2 = slow
while(index1 !== index2){
index1 = index1.next;
index2 = index2.next
}
return index1
}
}
return null;
};
