首先须要理解链表的概念
先把 next 记录下来
无论是插入，删除，还是翻转等等操作，先把 next 指针用长期变量保存起来，这能够解决 90% 重组链表中指向出错的问题，
如果不晓得什么时候须要用到守卫，那就都用
类型守卫 emptyNode 是创立的一个空的节点，并将它连贯到 head 节点之前，无论链表进行任何操作， emptyNode 都指向最初的头节点，是一个很实用的小办法，如果不晓得什么时候用，什么时候不必，那就先都用起来吧；
其实在大部分时候，emptyNode 都是能用上，即使只是遍历查找值，用上作为第 0 个值，当要找第 k 个值的时候，也不须要再判空解决啊
头节点判空解决
如果懒或者常常遗记看题目的给定条件，头节点判空都做起来，对于一些翻转题，还得将 head.next 也判断起来；
到纯熟之后，其实能够不做，然而用上最多就节约一段代码，也还好
画图，画图，画图
遇事不决的时候，还是要画图，一步一步的连起来，总可能捋分明的，画图是链表的关键所在
链表的节点是保留在内存中的一个数据结构
链表是一个特定的数据结构，在 JS 中能够体现为一个领有 val 和 next 属性的对象，所以遇到形如替换两个链表节点的时候，千万不能替换两个链表的 val 值，尽管 LC 有一些题是能够过，然而实际上是不合理的，而且一旦呈现这种思维，对于一些经典题 160. 相交链表 就会了解不了；
记住，链表是一个数据结构，不是一个值，能够类比成一个对象，替换链表比方不是简略替换值；
都是中等题
这里选的都是依照 LC 炽热排序，中等难度的题，感觉纯链表学习做特地难没太大必要，毕竟我只是一个菜鸟，大佬们能够自由选择，一起 ，进大厂；
具体题解
剑指 Offer 24. 反转链表
剖析
- 留神爱护好下一个节点 next
- 而后一直保护上一个节点和以后阶段，一直往后推即可
var reverseList = function (head) { let prev = null; while (head) { const next = head.next; head.next = prev; prev = head; head = next; } return prev;};面试题 02.05. 链表求和
剖析
- 这题是头对齐，445. 两数相加 II 是尾对齐，对于头对齐而已，链表比拟容易进行进位后间接构建成链表。
- 当两个链表都存在的时候，共有三个值须要相加，别离是 l1.val + l2.val + isUpper
- 当其中一个链表走完了，就只剩下一个链表和 isUpper, 须要留神的是，咱们不晓得哪个链表更长，所以须要判断一下
- 链表遍历完了，还要判断一下 isUpper 是否还有，还有就得再进一个节点
- 反转的数据结构就是 O(n+m)
/** * @剖析 * 1. 这里的返回值是依照十进制计算后的 `链表` */var addTwoNumbers = function (l1, l2) { const emptyNode = new ListNode(); let current = emptyNode; let isUpper = 0; // 是否满10，为前面的位+1 while (l1 && l2) { let sum = l1.val + l2.val + isUpper; if (sum >= 10) { isUpper = 1; sum = sum % 10; } else { isUpper = 0; } current.next = new ListNode(sum); current = current.next; l1 = l1.next; l2 = l2.next; } let l3 = l1 || l2; //残余的那个链表 while (l3) { let sum = l3.val + isUpper; if (sum >= 10) { isUpper = 1; sum = sum % 10; } else { isUpper = 0; } current.next = new ListNode(sum); current = current.next; l3 = l3.next; } if (isUpper) { // 遍历完了，如果还有进位 current.next = new ListNode(isUpper); current = current.next; } return emptyNode.next;};445. 两数相加 II
剖析
- 这题是尾对齐，面试题 02.05. 链表求和 是头对齐，对于头对齐而已，链表比拟容易进行进位后间接构建成链表。
- 所以这题先把两个链表反转，而后用面试题 02.05. 链表求和 形式组合完，再反转回去即可
- 当然咱们能够用数组或其余额定的数据结构来保留两数之和，最初再对立解决，然而因为是链表专题，所以除了不必额定的数据结构解决
- 反转的数据结构就是 O(n+m)
var addTwoNumbers = function (l1, l2) { const emptyNode = (current = new ListNode()); // 翻转量个链表，让他们头节点对齐 let temp1 = reverseList(l1); let temp2 = reverseList(l2); let isUpper = 0; // 是否满10，为前面的位+1 while (temp1 && temp2) { let sum = temp1.val + temp2.val + isUpper; if (sum >= 10) { isUpper = 1; sum = sum % 10; } else { isUpper = 0; } current.next = new ListNode(sum); current = current.next; temp1 = temp1.next; temp2 = temp2.next; } let l3 = temp1 || temp2; //残余的那个链表 while (l3) { let sum = l3.val + isUpper; if (sum >= 10) { isUpper = 1; sum = sum % 10; } else { isUpper = 0; } current.next = new ListNode(sum); current = current.next; l3 = l3.next; } if (isUpper) { // 遍历完了，如果还有进位 current.next = new ListNode(isUpper); current = current.next; } return reverseList(emptyNode.next);};// 反转链表var reverseList = function (head) { let prev = null; while (head) { const next = head.next; head.next = prev; prev = head; head = next; } return prev;};参考视频：传送门
61. 旋转链表
剖析：
- 从链表尾部阶段 k 长度，拼在后面即可 -- 其中 k = (K %len) ，如果挪动了 len 的地位，就又回到了原来的地位了
- 须要留神的是一些边界条件，然而这里间接定义 prev 为平安守卫，所有须要保留或者拼接的节点都利用 prev 来解决，就能够防止 cur 为 null 的时候无奈获取 next 指针的难堪，因为 cur 是理论走的指针，prev 只是一个平安守卫，它始终是存在的。
- 工夫复杂度O(N)
var rotateRight = function (head, k) { // 先求链表的长度 let len = 0, tempNode = head; while (tempNode) { len++; tempNode = tempNode.next; } // 须要位移 size 到头节点 let size = len - (k % len); let prev = new ListNode(); prev.next = head; let cur = head; while (size--) { cur = cur.next; prev = prev.next; } //保留挪动之后的尾部节点 let tail = prev; // 持续往前走 while (cur) { cur = cur.next; prev = prev.next; } // 原来的尾结点和头节点相连 prev.next = head; // 获取挪动后的头节点 const next = tail.next; // 尾结点的 next 指针指向的是 null tail.next = null; return next;};82. 删除排序链表中的反复元素 II
剖析
- 删除曾经排好序的链表的反复节点，最初返回一个新的链表
- 须要留神的是，这里是删除所有反复的节点，而不是保留一个值，即 1-2-2-3 将反复的 2 节点全副删除，失去 1-3
- 所以在遍历 head 的时候，须要分两种状况，一个是 head 的下一个节点有值且与 head 的值相等时，head 本人往下走，晓得 head.next === null 或者 head.next.val !== head.val 为止
- 如果是删除节点后，本次遍历须要重新整理 prev 节点和 head 节点
- 如果是一般遍历，则失常走即可
- 工夫复杂度:O(N)
var deleteDuplicates = function (head) { let emptyNode = (prev = new ListNode()); emptyNode.next = head; while (head) { while (head.next && head.val === head.next.val) { head = head.next; } if (prev.next !== head && head.val === prev.next.val) { // 这是遇到反复值时，删除节点后进行整顿， prev.next 从新指向新的 head 节点 head = head.next; // 从新连接起来 prev.next = head; } else { // 这是失常没有反复值走 prev = prev.next; head = head.next; } } return emptyNode.next;};86. 分隔链表
剖析
- 遍历链表找出值大于等于 x 的第一个节点 K，然这个时候后面那些节点都不必动了，因为都是小于 x 的
- 而后从 K 开始找出小于 x 的节点，挪动到 K-1 - K 之间的地位即可
- 因为存在插入和删除操作，所以须要用到 prev 指针和 cur 指针；因为可能存在第一个节点就是大于等于 x 的 K ，所以须要平安守卫 emptyNode
- 工夫复杂度 O(N)
留神：面试题 02.04. 宰割链表 这道题和本题相似，然而不保留每个分区的初始绝对地位
var partition = function (head, x) { let emptyNode = (prev = new ListNode()); emptyNode.next = head; while (head && head.val < x) { head = head.next; prev = prev.next; } // 走完了，或者遇到了 K,保留一下这个前置节点 let tail = prev; // 这个时候找到小于 x 的就要解决了 while (head) { if (head.val < x) { const next = head.next; // 插入到 tail 和 tail.next 之间 head.next = tail.next; tail.next = head; tail = tail.next; // 删除 head 节点,从新设置新的 head prev.next = next; head = next; } else { head = head.next; prev = prev.next; } } return emptyNode.next;};109. 有序链表转换二叉搜寻树
剖析
- 这里说的高度均衡，说人话其实就是尽可能均匀的将节点调配到左右子树中，那么找出两头节点，而后平分到左右节点树就是比拟适合的解
- 这种设置节点而后最初成树的操作，应用自底向上的思路就很适合，一直二分切割链表，晓得只有一个节点的时候就作为叶子节点，而后返回去
- 这里应用快慢指针找到两头节点 slow ， 留神这个节点是向上取中点的，所以就是以后节点的值，而后将后面一段链表分给左树，左边一段链表分给右树
- 这里用到了 BST 中左树节点永远小于根节点小于右侧节点的个性，以及本轮链表就是单增链表的个性
- 工夫复杂度 O(N) 还是相当于遍历一个残缺的链表
var sortedListToBST = function (head) { const recursion = (head) => { if (!head) return null; // 空节点 // 应用双指针找出两头节点 -- 这是向上取整 let emptyNode = (prev = new ListNode()); prev.next = head; let slow = (fast = head); while (fast && fast.next) { slow = slow.next; fast = fast.next.next; prev = prev.next; } // 以 slow 为根节点，左侧一段离岸边要截断 prev.next = null; const node = new TreeNode(slow.val); node.left = recursion(emptyNode.next); node.right = recursion(slow.next); return node; }; return recursion(head);};142. 环形链表 II
剖析
- 相比于 141. 环形链表 岂但要判断是否有环，还得算出入环的那个节点
- 这里进行的一系列计算，都必须保障终点是一样的，这样能力保障走进去的门路长度是适宜的。
- 画图可得，将起始点到环终点记作 l , 环长 r, 快慢指针相交的点间隔环终点为 s, 因为快指针是慢指针速度的 2 倍,依据速度肯定能够失去等式 s = (n-2m)r-l 其中 n,m 是快慢指针走的环的圈数量，这两个变量不重要，只须要示意他们别离走了 n, m 圈后相交了
- 这个时候咱们发现如果原来的慢指针持续走到环节点，须要走的途程是 (r-s) = (1-n+2m)r+l ;这个时候咱们在起始点从新开启一个新的慢节点 newSlow, 让他们一起走一段路 l, 他们切好在终点相遇
- 工夫复杂度 O(N)
var detectCycle = function (head) { if (!head) return null; //一个节点都没得，还有啥环 const emptyNode = new ListNode(); emptyNode.next = head; let slow = (fast = emptyNode); // 相当于走了走了一次了 while (fast && fast.next) { // 一开始都是从边界守卫开始，这样能够避免在第一个节点就有环了 slow = slow.next; fast = fast.next.next; if (slow === fast) { // 在环中的某一个点相交了 let newSlow = emptyNode; while (slow !== newSlow) { newSlow = newSlow.next; slow = slow.next; } return newSlow; } } return null; //如果会跳进去，证实无环};147. 对链表进行插入排序
剖析
- 编辑读写指针，write 指针前是排好序的链表，即它的是后面链表的最大值
- read 指针遇到比 write 指针值大于等于的节点，则 write 指针跟着挪动；遇到小于 read 的指针，删除节点并在 write 指针前找到一个适合的地位插入
- 工夫复杂度 O(nlogn)
var insertionSortList = function (head) { if (!head || !head.next) return head; let emptyNode = new ListNode(); emptyNode.next = head; let write = head, read = head.next; while (read) { if (read.val >= write.val) { // 读指针比写指针更大的时候，一起走 read = read.next; write = write.next; } else { // 删除 read 指针，而后从 emptyNode 到 write 中找个地位插入 // 先删除 -- 这个时候 read 指针先当做一个一般节点应用,留神: write 指针其实始终都在 read 之后，和 prev 指针的作用差不多 write.next = read.next; let em = emptyNode; while (em.next.val < read.val) { em = em.next; } // 插入 em.next >= read.val , 所有插入到 em - read - em.next read.next = em.next; em.next = read; // 把 read 指针放回到 write 之后，再持续走 -- 这里当然能够用长期遍历解决，然而 read = write.next; } } return emptyNode.next;};328. 奇偶链表
剖析
- 这里的奇偶性是排序奇偶性，类比数组的下标的奇偶性，而并非是值的奇偶性
- 原地转移且要放弃奇偶节点的绝对程序，也就是不能间接将奇偶节点替换地位，只能插入： 1-2-3-4-5 只能是 1-3-5-2-4 而不能是 1-3-5-4-2
- 依然应用快慢指针，快指针从初始地位启动，每次走 2 步，也就是说 fast 指针指向奇数节点，slow 指针指向匹配好全奇的尾结点
- 每次将 fast 节点删除，而后插入到 slow 节点之后，因为整体长度是不变的，所以 fast 节点删除后要放弃在奇数地位，就得设在长期的 prev 节点上
var oddEvenList = function (head) { if (!head || !head.next) return head; // 两个节点都没得，间接回家吧 let emptyNode = new ListNode(); emptyNode.next = head; let fast = (slow = head); while (fast && fast.next) { // 这是fast的前一个节点，用来删除 fast 节点 -- 同时作为在后面插入删除节点后，从新锚点的地位 const prev = fast.next; fast = fast.next.next; if (fast) { // 删除 fast 节点 prev.next = fast.next; fast.next = slow.next; slow.next = fast; slow = slow.next; // 复原 fast fast = prev; } } return emptyNode.next;};160. 相交链表
剖析
- 长度不一样的链表，必定不会在起始节点就相交，这是必然，所谓相交链表，就是这个子链表是齐全一样的，能够假如有 a,b,c 三个链表，而后 a,b 的尾结点同时指向 c, 即 aTail.next = c , bTail.next = c ，这个时候造成的新的链表 headA 和 headB 的相交链表就是 c
- 须要留神的是， aTail 和 bTail 可能会存在值相等，然而理论缺不是一个节点的状况，然而在 LC 的链表序列化中以数组的模式存在，就会蛊惑为什么不是在 aTail 这个节点就是相交节点，须要
特地留神 - 所以咱们一起走两个链表，直到其中一个完结，找出可能剩下没走完的那个链表，就能够判断除 long 长链表和 short 短链表, 以及残余未走的链表 tempC，如何让 long 和 tempC 一起走完，这个时候 long 和 short 长度就统一了，能够开始判断相交性
var getIntersectionNode = function (headA, headB) { let tempA = headA, tempB = headB; while (tempA && tempB) { // 一起走 tempA = tempA.next; tempB = tempB.next; } // tempC 是剩下的， long 是更长的链表 if (tempA) { tempC = tempA; long = headA; short = headB; } else { tempC = headB; long = headB; short = headA; } // 将 long 多进去的节点先走完，失去和 short 雷同长度的链表 while (long) { while (tempC) { tempC = tempC.next; long = long.next; } } while (long) { if (long === short) return long; long = long.next; short = short.next; } return null;};剖析 -- 压缩一下
- 原理根本是统一的，都是用长期变量分辨走 headA 和 headB， 而后判断是否存在雷同的点，如果最初走完了还没有，则返回 null -- 指标就是实现两个长度相等的链表，再比拟
- 如果 headA 和 headB 长度统一，那么一开始就遍历两个链表，并找出是否相交，如果相交则跳出循环，返回相交节点；如果没有相交节点，则一起走到 null，也跳出循环，返回 null
- 如果 headA 和 headB 长度不统一,那么就先一起遍历完结，短链表变量 A 切换到长链表 long，持续和剩下的原长链表多出的表走，直到长链表变量 B 切换到短链表 short，此时变量 A,B 对应的链表长度曾经相等，持续遍历，而后进行步骤 2 的判断
- 工夫复杂度 O(n+m)
var getIntersectionNode = function (headA, headB) { let tempA = headA, tempB = headB; while (tempA !== tempB) { tempA = tempA ? tempA.next : headB; tempB = tempB ? tempB.next : headA; } return tempA;};1721. 替换链表中的节点
剖析
- 先用双指针求出正序第 k 个节点 first 和反序第 k 个节点 second
- 当初要替换 first 和 second ， 须要先判断他们两个节点是不是相邻，相邻节点能够间接解决
- 如果不是相邻节点，那么就用删除插入的办法，将两个节点进行替换
- 留神: 当 first 和 second 求到之后，间接将外面的 val 值批改，在 leetcode 上是能够走通的，然而这其实是不合乎题意的，这就和相交链表 中的蛊惑一样，为什么 a2 节点值明明一样，然而相交节点缺是 a3 是一样的；替换了值，然而节点在存储地位是不变的，所以真是节点并没有扭转，这算是 LC 在这题中 ，边界设计有问题吧
- 对于 JS 来说，咱们个别能够用对象来模仿链表的节点，从这个方面看，每个节点都是独自的对象，外面有一个属性 val，咱们申明了两个对象，val 是一样的，然而他们却是不同的对象，因为他们在内存中存储的地位是齐全不一样的。
var swapNodes = function (head, k) { if (!head) return head; let emptyNode = new ListNode(); emptyNode.next = head; let pFirst = emptyNode; let first = head; while (--k) { first = first.next; pFirst = pFirst.next; } // 当初 first 就是正向第 k 个节点,只须要保留 let temp = first.next; let pSecond = emptyNode; let second = head; while (temp) { temp = temp.next; pSecond = pSecond.next; second = second.next; } // 这个时候 second 就是反向第 K 个节点 if (first.next === second) { // 相邻节点替换 pFirst.next = second; first.next = second.next; second.next = first; } else if (second.next === first) { // 相邻节点替换 pSecond.next = first; second.next = first.next; first.next = second; } else { // 替换 first 和 second const fNext = first.next; const sNext = second.next; pFirst.next = second; pSecond.next = first; second.next = fNext; first.next = sNext; } return emptyNode.next;};725. 分隔链表
剖析
- 两个关键点，每一个局部尽可能均匀，后面的链表长度大于前面的链表长度
- 间接计算出链表长度，取除数能够失去最短长度 n，取余能够晓得后面 m 个链表的长度要为 n+1
- 再一次遍历链表，应用读写指针宰割好，保留到数组中
var splitListToParts = function (head, k) { if (!head) return new Array(k).fill(null); // 没有节点也要切，只是切成 k 份的 null let emptyNode = new ListNode(); emptyNode.next = head; let temp = head; let len = 0; while (temp) { len++; temp = temp.next; } const n = Math.floor(len / k); let m = len % k; // 前 m 个链表取 n+1 个值 let write = (read = head); let ret = []; let other = k - m; // 插入 m 个 n+1 的链表 while (m--) { let count = 0; //前 m 个值,起码都还有一个值 while (count < n) { read = read.next; count++; } // 此时 read 指针在切割指针的地位 const next = read.next; read.next = null; //切割 ret.push(write); write = next; read = next; } // 再插入 k-m 个 n 长度的链表 while (other--) { if (n === 0) { ret.push(null); } else { let count = 0; while (count < n - 1) { read = read.next; count++; } // 此时 read 指针在切割指针的地位 const next = read.next; read.next = null; //切割 ret.push(write); write = next; read = next; } } return ret;};817. 链表组件
剖析
- 这里阐明了 head 中的值都是惟一的，且 nums 中的值都是 haed 值中的子集，所以能够另开一个 [0,N-1] 的数组，将 nums 的值作为下标放进去
- 这样就能够间接用数组下标判断 head 中的值是否蕴含在 nums 中，且复杂度为 O(1)
- 最初返回值是有多少个组件，也就是一旦断开链表，组件数量就加一
- 工夫复杂度 O(N) ; 空间复杂度 O(N)
var numComponents = function (head, nums) { const arr = []; for (let num of nums) { arr[num] = 1; } let len = nums.length; let ret = 0; let count = 0; //每一个组件的长度 -- 必须大于 1 能力组成一个组件 while (head && len) { if (arr[head.val]) { // nums 的值在缩小，一旦为 0 了，就完结遍历了 count++; // 万一需要求最大组件，就能够用这个 count 了 len--; } if (count && !arr[head.val]) { // 处于匹配状态，然而这一次却没有匹配值 ret++; count = 0; // 复原到 0, 持续下一次的匹配 } head = head.next; } return count ? ret + 1 : ret; //弹出遍历时如果还存在有匹配的组件没计算，则再加1};707. 设计链表
剖析
- 既然是设计题，而且设计的是链表，那么自然而然想起与之绝对应的数组，所以这里是用数组类模仿链表的
- 这里设计了获取链表第 k 个值，增加头，增加尾，增加 index 地位的节点以及删除第 index 节点的 api
- 按要求设计即可，留神边界即可；
/** * @剖析 * 1. 这里是用数组来模仿链表 */var MyLinkedList = function () { this.data = [];};/** * @剖析 -- 获取第 index 个节点的值 * 1. 这里的 index 类比数组的下标值，是从 0 开始的，也就是 index 为 0 代表头节点 * 2. 这里是获取第 index 个节点的值，如果没有这个 index，即 index 超出链表长度 len-1，返回 -1 */MyLinkedList.prototype.get = function (index) { const size = this.data.length; return index < size ? this.data[index] : -1;};/** * @剖析 -- 从头部插入一个链表值 */MyLinkedList.prototype.addAtHead = function (val) { this.data.unshift(val);};/** * @剖析 -- 从尾部插入一个链表值 */MyLinkedList.prototype.addAtTail = function (val) { this.data.push(val);};/** * @剖析 -- 从 index 插入一个值 */MyLinkedList.prototype.addAtIndex = function (index, val) { const len = this.data.length; if (index <= len) { if (index <= 0) { this.data.unshift(val); } else if (index === len) { this.data.push(val); } else { this.data.splice(index, 0, val); //在 index 节点删除 0 个值，并退出 val } }};/** * @剖析 -- 删除第 index 个值 */MyLinkedList.prototype.deleteAtIndex = function (index) { const len = this.data.length; if (index >= 0 && index < len) { this.data.splice(index, 1); }};1171. 从链表中删去总和值为零的间断节点
剖析 -- 暴力解法
- 间接两个循环遍历链表，失去所有链表组合的和，遇到 0 的，刷新外层指针的 next ，达到删除的成果
- 类比于数组，相当于将数组中和为 0 的间断子数组删除，失去剩下的数组，所以能够开两个循环，动静获取数组的长度，一旦遇到符合要求的数组，就删除，直到外层遍历完结为止
- 画图会比拟容易看到，值得注意的是，肯定要有一个指针 outer 从 head -> tail , 而后每一次都有长期指针 inner 从 outer.next 开始走到 tail
- 最差就不须要删除，所以要走 1+2+3+...n = O(N2)
var removeZeroSumSublists = function (head) { let emptyNode = new ListNode(); emptyNode.next = head; let sum = 0; let outer = emptyNode; while (outer) { let inner = outer.next; while (inner) { // 每次都由 inner 来判断是否要删除相应的链表 // outer 相当于是外围的一个 prev 指针，一旦某一个链表须要删除，间接 outer.next = 删除节点的下一个节点 即可 sum += inner.val; inner = inner.next; if (sum === 0) { // outer -> inner 的节点都要删除 outer.next = inner; sum = 0; //返回 } } // outer 也须要一直遍历到 tail outer = outer.next; // 每一次遍历时，长期总和要重置 sum = 0; } return emptyNode.next;};1019. 链表中的下一个更大节点
剖析 -- 双指针
- 写指针 w 遍历整个链表，读指针 r 找到第一个比以后 w 大的节点，并返回对应的值，如果 r 走残缺个链表没找到，则返回 0
- 这题和上一题一样，都是循环遍历，找到符合要求的值，而后间接返回
- 工夫复杂度 O(n2)
var nextLargerNodes = function (head) { if (!head) return []; let ret = []; while (head) { let r = head.next; let temp = 0; while (r) { if (r.val > head.val) { temp = r.val; break; } r = r.next; } ret.push(temp); head = head.next; } return ret;};1669. 合并两个链表
剖析
- 用 list2 来替换链表 a->b
- 须要留神，这里的 a 和 b 是下标为 a,b 的节点，第一个节点的坐标为 0，能够类比数组的下标；
- 找出 a 的前缀节点 prev 和 b 的下一个节点 next，而后用 prev.next = list2, 遍历 list2 到 tail2, tail2.next = next 即可
- 这里 list1 和 list2 的长度曾经做了限度，所以不须要做边界了
- 工夫复杂度 O(n+m)
var mergeInBetween = function (list1, a, b, list2) { const emptyNode = new ListNode(); emptyNode.next = list1; let prev = (next = emptyNode); //这个时候 prev 和 next 都是空节点，而 list1 的 head 节点对应的 index 是0，所以初始化为 -1 let index = -1; // 不取 = 的时候，失去的就是 下标为 b 的节点， while (index <= b) { if (index < a - 1) { // 这里是为了取下标为 a 节点的前一个节点 prev prev = prev.next; } next = next.next; index++; } // 这个时候 index 是b+1, 所以 next 是 b 的下一个节点 // 插入 list2 prev.next = list2; while (list2 && list2.next) { list2 = list2.next; } // 这个时候的 list2 曾经到了 tail list2.next = next; return emptyNode.next;};剑指 Offer 35. 简单链表的复制
剖析
- 因为要复制一个链表，所以所有 head 上节点其实都曾经不能应用了，须要从新创立新的 Node 节点，而后对应的 next 和 random 也须要是新的节点，而不是 head 曾经保留好的。
- 因为新的节点 next 指针指向的节点还没创立，对应的 random 节点无奈确定，所以应用 map 先保留一份单个值的节点，其中 key 是旧的 Node 节点，value 是新创建的节点
- 而后再遍历 head 链表，找到就节点的复制节点，，为它指向新的 next 和 random
- 这里为啥用 weakMap 而不是 map 呢，这就是面试的另外一个问题了，能够查看一下 map 和 weakMap 的区别，这里次要是和 key 为对象时，打消 map 后的垃圾回收机制无关
- 工夫复杂度O(N)
var copyRandomList = function (head) { if (!head) return head; const map = new WeakMap(); let temp = head; while (temp) { // key 是旧节点，value 保留一个新的节点 map.set(temp, new Node(temp.val)); temp = temp.next; } // 开始复制 temp = head; while (temp) { const node = map.get(temp); //这个是一个新的节点，它的 next 和 random 也要是新的，存在 map 中 node.next = map.get(temp.next) || null; node.random = map.get(temp.random) || null; temp = temp.next; } return map.get(head);};25. K 个一组翻转链表
- 既然是翻转，必定是须要用到空节点;
- 一次遍历，计算链表长度，看看须要翻转多少次
- 因为须要翻转屡次，每一次翻转须要用到的变量:
- outerPrev -- 每一次翻转前一个节点，用来和翻转后的头节点连贯
- cur 示意的翻转链表时以后节点，prev 是遍历到的前一个节点
- step 示意翻转了多少次，因为初始化时 cur 是第一个节点，所以能够翻转 k 次；
- 翻转完结后，cur 示意下一次翻转的头节点，prev 是翻转后的头节点，tempHead 是保存起来的翻转前头节点，当初是翻转后的尾节点，也是下一轮翻转的前一个节点；所以将他们连接起来： outerPrev.next = prev，tempHead.next = cur;
- 更新一下 outerPrev
- 工夫复杂度 O(N)
var reverseKGroup = function (head, k) { if (!head.next || k < 2) return head; const emptyNode = new ListNode(); emptyNode.next = head; let len = 0; let cur = head; while (cur) { len++; cur = cur.next; } let count = Math.floor(len / k); //须要翻转的次数 cur = head; let outerPrev = emptyNode; //每次翻转链表的前一个节点 while (count--) { let tempHead = cur; // 翻转链表的长期链表头 let prev = outerPrev; let step = 0; //每一次翻转走的步数 while (step < k) { const next = cur.next; cur.next = prev; prev = cur; cur = next; step++; } // 翻转好了，内部prev 和翻转后的头节点相连 outerPrev.next = prev; tempHead.next = cur; // 更新内部prev 为长期头节点 outerPrev = tempHead; } return emptyNode.next;};