[TOC] # 1.链表中倒数第 k 个节点 [牛客网链接](https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 题目描述：输入一个链表，输出该链表中倒数第 k 个结点。 解题思路：两个指针，一个往前移动，另一个保持在往前移动的指针的前 k 位置处，前一个指针到达末尾时后一个指针所指结点为倒数第 k；同时用 count 判断 k 是否比链表中元素还多，多就返回 null。 ```js function FindKthToTail (head, k) { // write code here let first = head, second = head let count = 0 // 链表中元素个数 while (head !== null) { count++ if (count > k) { second = second.next } head = head.next } return k > count ? null : second } ``` # 2.反转链表 [牛客网链接](https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 题目描述：输入一个链表，反转链表后，输出新链表的表头。 解题思路：三个指针，curr 指向当前节点，prev 指向前一个，next 保存当前节点的下一个结点，next = curr -> next ，curr -> next = prev ，prev = curr ，curr = next ```js /* function ListNode(x){ this.val = x; this.next = null; }*/ function ReverseList (pHead) { // write code here if (pHead === null) return null let prev = null, curr = pHead, next while (curr !== null) { next = curr.next curr.next = prev prev = curr curr = next } return prev } ``` # 3.合并两个排序的链表 [牛客网链接](https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 解题思路：首先注意一下如果有一个链表为 null 则直接返回另一个链表，两个指针指向两个链表，比较大小来确定 next，最后记得合并剩下的即可。 ``` // 递归版本，不创建新的节点 function Merge(pHead1, pHead2) { // write code here if (pHead1 === null) return pHead2 if (pHead2 === null) return pHead1 let pNode if (pHead1.val < pHead2.val) { pNode = pHead1 pNode.next = Merge(pHead1.next, pHead2) } else { pNode = pHead2 pNode.next = Merge(pHead1, pHead2.next) } return pNode } ``` # 4.复杂链表的复制 [牛客网链接](https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 解题思路：  ```js function RandomListNode(x){ this.label = x; this.next = null; this.random = null; } function Clone(pHead) { /* 1、复制每个节点，如：复制节点 A 得到 A1，将 A1 插入节点 A 后面 2、遍历链表，A1 -> random = A -> random -> next; 3、将链表拆分成原链表和复制后的链表 */ if (!pHead) return null let currNode = pHead while (currNode) { let newNode = new RandomListNode(currNode.label) newNode.next = currNode.next currNode.next = newNode currNode = newNode.next } // step2 currNode = pHead while (currNode) { let tmpNode = currNode.next if (currNode.random) { tmpNode.random = currNode.random.next } currNode = tmpNode.next } // step3: 拆分 let pCloneHead = pHead.next let tmp currNode = pHead while (currNode.next) { tmp = currNode.next currNode.next = tmp.next currNode = tmp } return pCloneHead } ``` # 5.二叉搜索树与双向链表 [牛客网链接](https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking) 题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 解题思路：非递归的中序遍历解法，用一个 pre 指针记录上一个结点，稍微注意下一开始的 pre 为 null，弹出到第二个再做指针操作，另外注意这里的指针改变不会影响后续的中序遍历；first 用于确定最后返回的链表的表头结点是哪个（第一个弹出的） ```js /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function Convert(pRootOfTree) { // write code here if (pRootOfTree === null) return let root = pRootOfTree let pre = null // pre保存上一个结点 let first = true const stack = [],queue = [] while (true) { while (root !== null) { stack.push(root) root = root.left } if (stack.length === 0) { break } let p = stack.pop() if (first) { pRootOfTree = p first = false } if (pre){ pre.right = p p.left = pre } pre = p root = p.right } return pRootOfTree } ``` # 6.两个链表的第一个公共结点 题目描述：输入两个链表，找出它们的第一个公共结点。 解题思路：如果两个链表有公共结点，那么长的链表长度 – 短的链表长度 = 需要多走的步数；长的链表多走这么多步，然后两个指针一起走，直到走到第一个公共结点 另外注意对链表的形状的理解：Y型而不是X型  ```js function FindFirstCommonNode(pHead1, pHead2) { // write code here // 先遍历获取两个链表的长度 let len1 = 0, len2 = 0 let p1 = pHead1, p2 = pHead2 while (p1 !== null) { len1++ p1 = p1.next } while (p2 !== null) { len2++ p2 = p2.next } // 长的先走相差的步数，然后同时走 p1 = pHead1, p2 = pHead2 if (len1 >= len2) { let dis = len1 - len2 while (dis--) { p1 = p1.next } } else { let dis = len2 - len1 while (dis--) { p2 = p2.next } } while (p1 !== p2) { p1 = p1.next p2 = p2.next } return p1 } ``` # 7.链表中环的入口结点 题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null。 解题思路： 方案1：如果链表中的 val 都不相等，可以用一个 HashMap 来存储 val，遇到的第一个已经在 HashMap 中存在的 val 那么这个结点就是环的入口 ```js function EntryNodeOfLoop(pHead) { // write code here let cur = pHead, obj = {}, label while (cur !== null) { label = cur.val if (!obj[label]) { obj[label] = 1 cur = cur.next } else { return cur } } } ``` 方案2： a、第一步，找环中相汇点。分别用 fast，slow 指向链表头部，slow 每次走一步，fast 每次走二步，直到 fast == slow 找到在环中的相汇点。 b、第二步，找环的入口。接上步，当 fast == slow 时，fast 所经过节点数为 2x,slow 所经过节点数为 x,设环中有 n 个节点，fast 比 slow 多走 r 圈有 2x = rn + x; x = rn;（r 为圈数，n 为一圈的结点数） 可以看出 slow 实际走了多个环的步数，再让 fast 指向链表头部，slow 位置不变。 假设链表开头到环接口的距离是 y，那么 x - y 表示 slow 指针走过的除链表开头 y 在环中走过的距离，那么 slow 再走 y 步，此时 fast 结点与 slow 结点相遇，fast == slow ，x-y + y = x = rn，即此时 slow 指向环的入口。  ```js function EntryNodeOfLoop(pHead) { // write code here if (pHead === null || pHead.next === null) return null let p1 = pHead, p2 = pHead while (p2 !== null && p2.next !== null) { p1 = p1.next p2 = p2.next.next if (p1 === p2) { // 快慢指针汇合了 p2 = pHead // 就让快指针移到链表头 while (p1 !== p2) { p1 = p1.next p2 = p2.next } if (p1 === p2) return p1 } } return null } ``` # 8.删除链表中重复的结点 题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 解题思路：注意新建一个头结点，返回这个头结点的 next，这个方法巧妙地解决了例如 1 1 1 1 1 这样的情况，大体思路是用三个指针，prev，curr，next，发现有相同的数字 next指针就一直走下去，最后 prev.next 指向 next 就相当于删除了这中间的结点 ```js function ListNode(x){ this.val = x; this.next = null; } function deleteDuplication(pHead) // 注意链表已排序 { // write code here if (pHead === null || pHead.next === null) return pHead // {1} 和 null 的特殊情况 let head = new ListNode(-1) // 新建一个头结点，以解决 1 1 1 1 1的情况 let prev = head, curr = pHead, next while (curr !== null && curr.next) { // 注意加个curr !== null 的条件 next = curr.next if (curr.val === next.val) { while (next && curr.val === next.val) { next = next.next } prev.next = next curr = next } else { prev.next = curr prev = curr curr = curr.next } } return head.next } ```