[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 } ```