study-notes链表
其实本来不想写链表的东西的，但是因为某一次面试中，链表题居然写不出来！！！气死我了
构建链表
构建链表，对于Js来说的话就是创建一个
function，直接上代码吧
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
注意使用虚头节点
虚头节点还是非常舒服的，对于处理一些边界条件非常nice
let dummyNode = new ListNode(-1,null)
模拟法
这个的话，用画图比较清晰，然后就是指针发生变化的时候最好要分清楚步骤和先后关系，还有就是变动后的顺序，不然容易出现指针乱指的情况，上题
反转链表
题目描述：原来是1->2->3->null，反转后3->2->1->null
solution
使用头插法，一个虚头节点，一个head指针用于遍历原来的链表，一个temp指针临时记录head.next，然后使用模拟头插法。
while(head){
// 临时存放
temp = head.next
// 模拟头插
head.next = dummyNode.next
dummyNode.next = head
// 回到原来链表的下一个位置，继续遍历
head = temp
}
两两交换链表中的节点
题目描述：原来是1->2->3->4，交换后为2->1->4->3
solution
模拟法，最好画图
var swapPairs = function(head) {
if(!head || !head.next){
return head;
}
// init
let dummyNode = new ListNode(-1,head)
// 变量声明
let temp1 = null;
let temp2 = null;
let cur = dummyNode;
while(cur.next && cur.next.next){
// 临时记录
temp1 = cur.next;
temp2 = cur.next.next;
// 1
cur.next = temp2;
// 2
temp1.next = temp2.next
// 3
temp2.next = temp1;
// 移动
cur = temp1;
}
return dummyNode.next;
};
快慢指针
一个fast指针，一个last指针，可以用于处理步长（距离）问题
相交链表
题目描述：找到两个链表相交的节点，如果没有则返回null
solution
假如相交：
- 设LA为A的头节点到相交节点的距离
- 设LB为B的头节点到相交节点的距离
- 设X为相交节点到尾节点null的距离
LA+X+LB，表示指针curA从链表A的头结点走到尾结点，回到链表B的头结点后走了LB的距离 LB+X+LA，表示指针curB从链表B的头结点走到尾结点，回到链表A的头结点后走了LA的距离 显然，上面两个距离相等，也就是说两个指针在相交点相遇了
假如不相交:
LA + LB = LB +LA 最终curA和curB都会指向尾节点null
var getIntersectionNode = function(headA, headB) {
let curA = headA
let curB = headB
while(curA != curB){
curA = curA ? curA.next:headB
curB = curB ? curB.next:headA
}
return curA
};
删除链表的倒数第 N 个结点
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
solution
这题的思路是快慢指针，首先假设链表的长度为L+1（虚头节点），要删除链表的倒数第N个节点，可以先让fast指针先走N，则还剩下L+1-N，然后让slow指针跟着fast一起走向最后一个节点（非空），那么slow指针刚好就是要删除的节点的前一个节点（这样更容易删除）。虚头节点是为了处理删除第一个元素的边界条件
var removeNthFromEnd = function(head, n) {
let dummyNode = new ListNode(-1,head);
let fast = dummyNode;
let slow = dummyNode;
while(n--){
fast = fast.next;
}
while(fast.next){
slow = slow.next;
fast = fast.next;
}
// 删除
let temp = slow.next;
slow.next = temp.next;
temp.next = null;
return dummyNode.next;
};
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
solution
fast指针每次走两步，slow指针每次走一步，那么他们总会在环中相遇，这个时候(x=z)
此时，在相遇点定义一个指针cur1，在头节点处定义一个cur2，每次都走一步，当两者相遇的时候就是环形入口的节点，此时直接返回
var detectCycle = function(head) {
// 定义快慢指针
let fast = head
let slow = head
// 遍历
while(fast && fast.next){
// slow走一步
slow = slow.next
// fast走两步
fast = fast.next.next
// 相遇点
if(slow === fast){
// x=z，也就是在相遇点定义一个指针，在头节点定义一个指针，共同走到环的入口
let cur1 = fast
let cur2 = head
while(cur1!==cur2){
cur1 = cur1.next
cur2 = cur2.next
}
return cur1
}
}
return null
};