反复遍历链表，尝试快慢指针和多指针
最近在看数据结构和算法，努力总结出道~
TL;DR
- 链表就是嵌套的对象，
{val:1,next:{val:2,next:...}} - 链表里的指针，听起来很抽象，其实就是部分链表，依旧是嵌套对象，p 是
{val:1,next:{val:2,next:...}} - 指针往后挪动，其实就是
p = p.next，也就是 p 变成{val:2,next:...} - 链表的最后一个节点，
next肯定是空的 - 处理链表的时候，一般为了边界问题，很多时候先创建一个空节点，指向链表，有备无患吧
- 删除节点必须要知道前置节点
- 反转链表就是反转指针
- 反复遍历链表的时候，考虑下快慢指针和多指针
练习：删除倒数第 n 个结点
网络异常，图片无法展示
|
先说说，初始想法：
链表里遍历，只能从前往后，所以删除倒数第 n 个结点，就是删除第len+1-n个，比如总共 5 个结点，删除倒数第 1 个结点，其实就是第 5 个结点，当然链表里删除节点需要知道前置节点，也就是知道倒数第n+1个结点。
于是遍历链表知道链表的长度，然后再遍历链接到第len-n个结点处开始删除第len+1-n个节点，但这样就是嵌套遍历。
怎么能一次遍历就能成功呢？
其实这里，想想双指针法，可以记录遍历的进度。
倒数第n+1个结点距离最后一个节点是n步，换言之，如果有两个指针相隔n步，那么前面的指针到达终点时，后一个指针恰好到了倒数第n+1的结点处，就可以顺手的删掉倒数第n个结点了。
这种两个指针，同个方向，一前一后，就是快慢指针法，解决差距的问题。
- 处理边界问题，提前创建空节点
- 快指针先走 n 步
- 然后快慢指针一起走，直到快指针走到终点，那么慢指针也就到了倒数第
n+1个结点处 - 删除后面一个节点
var removeNthFromEnd = function (list, n) { // 处理边界问题，加个空节点 let head = new ListNode(); head.next = list; // 定义快慢指针 let slow = head; let fast = head; // 快指针先走n步 for (let count = 0; count < n; count++) { fast = fast.next; } // 快慢一起走，直到快指针到终点，慢指针也就到了倒数第n+1个结点处 while (fast && slow && fast.next && slow.next) { fast = fast.next; slow = slow.next; } // 删除倒数第n个结点 slow.next = slow.next.next ? slow.next.next : null; return head.next; };
可以看下官方题解的其他方案
练习：反转链表
网络异常，图片无法展示
|
处理链表的本质，就是处理指针。
所以反转链表的本质，就是反转指针。
先看下只有两个结点的链表反转：1->2->null
const list = { val: 1, next: { val: 2, next: null } }; // null 1->2 // 建个空节点方便指定 let p0 = null; let p1 = list; // 把1后面的链表（这里只有2），先存下，p2就是{val:2,next:null} let p2 = p1.next; // 先把1的指针置空，p1就是{val:1,next:null} // 此时变成 1->null 2 p1.next = p0; // 再2的指针指向1，p2就是{val:2,next:p1} p2.next = p1;
三个结点的链表反转：1->2->3->null，其实道理是类似的，但是 p0 和 p1 指针向前移动。
网络异常，图片无法展示
|
var reverseList = function (list) { let pre = null; let cur = list; while (cur) { // 必须先保存下一个结点，不然置空cur指针之后，拿不到cur的下一个结点 let next = cur.next; // 反转cur指针 cur.next = pre; // pre和cur指针往前走 pre = cur; cur = next; } // cur为空的时候，说明pre就是首节点 return pre; };
练习：反转局部链表
网络异常，图片无法展示
|
这题的第一感觉是和上面的很像，只要先找到要反转的链表区间，然后反转，再重新连接就可以了。
// 官网的注释很明确，直接使用了 var reverseBetween = function (head, left, right) { // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 const head = new ListNode(); head.next = head; let pre = dummyNode; // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 // 建议写在 for 循环里，语义清晰 for (let i = 0; i < left - 1; i++) { pre = pre.next; } // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点 let rightNode = pre; for (let i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; } // 第 3 步：切断出一个子链表（截取链表） let leftNode = pre.next; let curr = rightNode.next; // 注意：切断链接 pre.next = null; rightNode.next = null; // 第 4 步：同第 206 题，反转链表的子区间 reverseLinkedList(leftNode); // 第 5 步：接回到原来的链表中 pre.next = rightNode; leftNode.next = curr; return dummyNode.next; }; const reverseLinkedList = (head) => { let pre = null; let cur = head; while (cur) { const next = cur.next; cur.next = pre; pre = cur; cur = next; } };
时间复杂度是 O(n)，空间复杂度是 O(1)。
但是这里遍历了两次列表，想想还能不能继续优化。
新思路：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。
网络异常，图片无法展示
|
根据上面的思路，写出代码
var reverseBetween = function (list, left, right) { let head = new ListNode(); head.next = list; let left_pre = head; // 将left_pre指针移到在前一个节点处，且以后一直在这个位置 for (let i = 0; i < left - 1; i++) { left_pre = left_pre.next; } // cur指针也始终不变 let cur = left_pre.next; // 反转right - left次 for (let i = 0; i < right - left; i++) { // next始终是cur的下一个节点 let next = cur.next; // 先修改cur的下一个指针指向 cur.next = next.next; // 然修改next的下一个指针指向 next.next = left_pre.next; // 最后修改left_Pre的下一个指针指向 left_pre.next = next; } return head.next; };
