24.两两交换链表中的节点
题目链接：
https://leetcode.cn/problems/swap-nodes-in-pairs/
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
思路：
对节点进行删除或者交换操作时需要当前节点之前的节点。本题交换两个相邻的节点需要两个指针，一个指向pre这两个节点之前的节点，另一个指针cur指向这两个节点中的第一个节点，便可完成交换。交换完后cur指向第二个节点，令pre = cur, cur = cur.next进行下一次交换，直到cur或者cur.next未定义（链表末尾或者多出一个节点）。为了避免单独对头节点进行讨论，可以设置哨兵节点。
代码：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
let cur = head
let dum = new ListNode(0, head)
let pre = dum
while(cur && cur.next){
let tmp = cur.next
cur.next = tmp.next
tmp.next = cur
pre.next = tmp
pre = cur
cur = cur.next
}
return dum.next
};
19.删除链表的倒数第N个节点
题目链接：
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路：
设置哨兵节点，从哨兵节点开始遍历n+1次。再定义一个指针pre指向头节点，这两个节点继续同步向后遍历，当后一个指针到末尾时，pre指针便指向倒数第n个节点。
代码：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let dum = new ListNode(0, head)
let cur = dum
let pre = cur
for(let i = 0; i <= n; i++){
cur = cur.next
}
while(cur){
cur = cur.next
pre = pre.next
}
pre.next = pre.next.next
return dum.next
};
160.相交链表
题目链接：
https://leetcode.cn/problems/intersection-of-two-linked-lists/
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路：
最直观的思路是先遍历A，通过集合的方式保存节点，再遍历B，出现集合中的元素就停止，此时的节点就是相交的节点。
更好的方法是使用双指针。设链表A、B未重合的部分长度分别为a，b，重合部分长度为c。
- 设置两个指针curA和curB分别从headA和headB出发，同时向后遍历。
- 如果遍历到末尾，下一次遍历就将指针移动到另一个链表的头部，两个指针相遇的节点就是相交节点，因为此时两个指针经过的节点数均为a+b+c。
同样地，为了避免对头结点单独讨论，给两个链表都设置哨兵节点，从哨兵节点开始遍历。为了能够辨别无相交的情况，指针遍历到末尾之后再移动到另一链表头部的操作只能做一次，之后如果再走到末尾，说明没有交点。
代码：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let curA = new ListNode(0)
curA.next = headA
let curB = new ListNode(0)
curB.next = headB
let chanceA = true
let chanceB = true
while(curA && curB){
if(!curA.next && chanceA){
curA = headB
chanceA = false
}
else{
curA = curA.next
}
if(!curB.next && chanceB){
curB = headA
chanceB = false
}
else{
curB = curB.next
}
if(curA === curB){
return curA
}
}
return null
};
142.环形链表Ⅱ
题目链接：
https://leetcode.cn/problems/linked-list-cycle-ii/
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
思路：
使用快慢指针。fast指针走两次，slow指针走一次。如果存在环，它们会在环中相遇。记head到环起点的长度为a，环起点到两指针相遇点的距离为b，从相遇点再走到到环起点的距离为c。
fast和slow一定会在slow走完环的第一圈之前相遇。原因是slow每走一步fast就会多走一步，而fast要和slow相遇需要多走一圈（b+c）。假设slow刚好沿着环走完一圈，此时fast比slow多走a+b+c，比环的一圈多。所以在此之前fast就和slow相遇了。
相遇时：
fast走的路程：a+(b+c)+b
slow走的路程：a+b
又因为fast走的路程是slow的两倍：fast=2slow
所以：a+(b+c)+b=2(a+b)
a=c
此时再让两个指针从head和相遇点同时移动，一定可以在环起点汇合。
代码：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
let cur = head
let dum = new ListNode(0, head)
let pre = dum
while(cur && cur.next){
let tmp = cur.next
cur.next = tmp.next
tmp.next = cur
pre.next = tmp
pre = cur
cur = cur.next
}
return dum.next
};
总结：
对链表上的节点进行操作，一定要控制其之前的一个节点。head节点总是很特殊，为了避免讨论特殊情况可以在之前增加一个哨兵节点，把哨兵节点当作头节点开始遍历以去除这种特殊性。
标签：head,ListNode,cur,day4,javascript,随想录,next,链表,节点 From： https://www.cnblogs.com/endmax/p/16906065.html