《剑指 Offer （第 2 版）》链表部分 JavaScript 题解
《剑指 Offer（第 2 版）》通行全球的程序员经典面试秘籍。剖析典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。
最近，把链表部分的题刷完了。本文来分享下这些题的解法
06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
「示例 1：」
输入：head = [1,3,2] 输出：[2,3,1]
「限制：」
0 <= 链表长度 <= 10000
题目地址：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
「运用栈的解题思路」
遍历链表，遍历的顺序是从头到尾，可输出的顺序却是从尾到头；也就是说第一个遍历到的节点最后一个输出，而最后一个遍历到的节点第一个输出。这个就是典型的后进先出，我们可以用栈来实现这种顺序，每经过一个节点的时候，把该节点放到一个栈中，当遍历完整个链表后，再从栈顶开始依次输出节点的值
/** * @param {ListNode} head * @return {number[]} */ var reversePrint = function(head) { let nodes = []; while (head != null) { nodes.push(head.val); head = head.next; } // 可以不用下面这一整段，直接 return nodes.reverse(); let result = []; let temp = nodes.pop(); while (temp != null) { result.push(temp); temp = nodes.pop(); } return result; };
18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
「注意：」此题对比原题有改动
「示例 1:」
输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
「示例 2:」
输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
「说明：」
- 题目保证链表中节点的值互不相同
- 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
题目地址：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
「解题思路」
遍历找到要删除的节点，将前一个节点的next指向后一个节点，最后返回头节点。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var deleteNode = function(head, val) { if(head === null) return null; if(head.val === val) return head.next; let tmp = head; while(tmp.next && tmp.next.val !== val){ tmp = tmp.next; } if(tmp.next.val === val){ tmp.next = tmp.next.next; } return head; };
22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
「示例：」
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
题目地址：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
「方法一：顺序查找」
「思路与算法」
最简单直接的方法即为顺序查找，假设当前链表的长度为 n，则我们知道链表的倒数第 k 个节点即为正数第 n−k 个节点，此时我们只需要顺序遍历到链表的第 n−k 个节点即为倒数第 k 个节点。
我们首先求出链表的长度 n，然后顺序遍历到链表的第 n−k 个节点返回即可。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var getKthFromEnd = function(head, k) { let node = head, n = 0; while (node) { node = node.next; n++; } node = head; for (let i = 0; i < n - k; i++) { node = node.next; } return node; };
「方法二：双指针」
「思路与算法」
快慢指针的思想。我们将第一个指针 fast 指向链表的第 k+1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针 fast 走到链表的尾部空节点时，则此时 slow 指针刚好指向链表的倒数第k个节点。
- 我们首先将 fast 指向链表的头节点，然后向后走 k 步，则此时 fast 指针刚好指向链表的第 k+1 个节点。
- 我们首先将 slow 指向链表的头节点，同时slow 与 fast 同步向后走，当 fast 指针指向链表的尾部空节点时，则此时返回 slow 所指向的节点即可。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var getKthFromEnd = function(head, k) { let fast = head, slow = head; while (fast && k > 0) { [fast, k] = [fast.next, k - 1]; } while (fast) { [fast, slow] = [fast.next, slow.next]; } return slow; };
24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
「示例:」
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
「限制：」
0 <= 节点个数 <= 5000
题目地址：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
「解题思路」
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let prev = null; let curr = head; while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; };
25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
「示例1：」
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
「限制：」
0 <= 链表长度 <= 1000
题目地址：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
「解题思路」
「双指针」
- 新建一个头结点 head，同时新增一个 node 结点表示现在新链表新加到的位置
- 通过判断 l1 和 l2 是否同时不为空来判断是否有一个链表已经遍历完
- 然后新链表接上 l1 或 l2 中还没遍历完的那个就行
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { const head = new ListNode(-1); let node = head; while(l1 && l2) { if (l1.val < l2.val) { node.next = l1; l1 = l1.next; } else { node.next = l2; l2 = l2.next; } node = node.next; } node.next = l1 || l2; return head.next; };
35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
「示例 1：」
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
「示例 2：」
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
「示例 3：」
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
「示例 4：」
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
「提示：」
-10000 <= Node.val <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
题目地址：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
「解题思路」
本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。
具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。
在实际代码中，我们需要特别判断给定节点为空节点的情况。
/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function(head, cachedNode = new Map()) { if (head === null) return null; const newHead = new Node(head.val, null, null); cachedNode.set(head, newHead); newHead.next = copyRandomList(head.next, cachedNode); newHead.random = cachedNode.get(head.random); return newHead; };
36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
「解题思路」
二叉搜索树的中序遍历便是升序的，自然而然的，我们便先中序遍历将节点保存下来，然后将他们相连成循环双向链表。
/** * // Definition for a Node. * function Node(val,left,right) { * this.val = val; * this.left = left; * this.right = right; * }; */ /** * @param {Node} root * @return {Node} */ var treeToDoublyList = function(root) { if (root === null) return null; const stk = [], nodeList = []; let node = root; while(stk.length || node) { while(node) { stk.push(node); node = node.left; } node = stk.pop(); nodeList.push(node); node = node.right; } nodeList.push(nodeList[0]); for(let i = 1; i < nodeList.length - 1; i++) { nodeList[i].right = nodeList[i + 1]; nodeList[i].left = nodeList[i - 1]; } nodeList[0].right = nodeList[1]; nodeList[0].left = nodeList[nodeList.length - 2]; return nodeList[0]; };
52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
「示例 1：」
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
「示例 2：」
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
「示例 3：」
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。
「注意：」
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
题目地址：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/****
「解题思路」
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果当前节点不在哈希集合中，则继续遍历下一个节点；
- 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都是两个链表的公共节点，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点，返回该节点。
- 如果链表headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { const visited = new Set(); let temp = headA; while (temp !== null) { visited.add(temp); temp = temp.next; } temp = headB; while (temp !== null) { if (visited.has(temp)) { return temp; } temp = temp.next; } return null; };
