今日学习：
24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
题目链接/文章讲解/视频讲解： https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
第一想法
想借用反转链表的思路来做题，但是遇到了点麻烦，于是先看了视频，意识到两两交换实际上涉及到三条线路的改变
这道题要用到虚拟头节点，要考虑奇偶性
/**
* 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) {
var listnode = new ListNode(null, head)
var current = listnode
//考虑奇偶性
while(current.next && current.next.next){
let temp = current.next
let temp1 = current.next.next.next
//两两交换，其实有三条线都在变
current.next = current.next.next
current.next.next = temp
temp.next = temp1
current = current.next.next
}
return listnode.next
};
19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
第一想法
遇到删除操作，一般需要运用虚拟头节点
删除操作，一般需要让指针指向要删除的节点的前一个
倒数第n个节点，可以通过快慢指针的移动得到，快指针先动n+1格，后快、慢指针一起运动到快指针指向null，此时慢指针刚好指向倒数第n+1个节点处，也就是删除节点的前一个
找到节点后，直接让该节点的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
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
var listnode = new ListNode(0, head)
var fast = listnode
var slow = listnode
n += 1
while(n-- && fast){
fast = fast.next
}
while(fast){
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return listnode.next
};
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
第一想法
首先考虑到两个链表长度不同，需要做到长度对齐
然后起头并进，找到第一个相同的节点，并返回
/**
* 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 a = headA
let b = headB
let la = 0
let lb = 0
while(a){
la++
a = a.next
}
while(b){
lb++
b = b.next
}
let large = headB
let small = headA
if(la > lb){
large = headA
small = headB
}
let length = Math.abs(la-lb)
while(length--){
large = large.next
}
while(large!==small&&large){
large = large.next
small = small.next
}
return large
};
142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
第一想法
这道题目有点难度，需要数学公式推导
首先要判断是否有环，定义一个快指针每次走两格，，一个慢指针每次走一格，如果快指针与慢指针相遇，那么说明有环，否则无环
如上图所示，快指针与慢指针相遇必然是在环内相遇，且会在慢指针的第一圈内相遇
整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了
当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
let fast = head
let slow = head
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
if (fast == slow) {
let index1 = slow
let index2 = head
while (index1 !== index2) {
index1 = index1.next
index2 = index2.next
}
return index1
}
}
return null
};
总结
链表问题在处理过程中，有时候需要使用虚拟头节点，有时候则不需要。一般来说，需要使用虚拟头节点的情况包括：
删除操作：当需要删除链表中的某个节点时，如果没有虚拟头节点，就需要分情况讨论，区分删除头节点和非头节点的情况；而有了虚拟头节点，就可以简化这个过程。
插入操作：在某些情况下，需要在链表中插入一个节点，如果没有虚拟头节点，就需要考虑是否是在头部插入节点，而有了虚拟头节点，就可以统一处理插入操作。
不需要使用虚拟头节点的情况包括：
只读操作：对于只需要遍历或者读取链表中的数据而不涉及插入和删除操作的情况，通常不需要虚拟头节点
