160.相交链表
https://leetcode-cn.com/problems/intersection-of-two-linked-lists
方法 1：暴力法
思路
对于链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。
复杂度
时间复杂度：O(M * N)O(M∗N), M, N 分别为两个链表的长度。 空间复杂度：O(1)O(1)。
var getIntersectionNode = function (headA, headB) { if (!headA || !headB) return null let pA = headA while (pA) { let pB = headB while (pB) { if (pA === pB) return pA pB = pB.next } pA = pA.next } }
方法 2：哈希表
思路
先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。 再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。
复杂度
时间复杂度：O(M + N), M, N 分别为两个链表的长度。 空间复杂度：O(N)，N 为链表 A 的长度。
var getIntersectionNode = function (headA, headB) { if (!headA || !headB) return null const hashmap = new Map() let pA = headA while (pA) { hashmap.set(pA, 1) pA = pA.next } let pB = headB while (pB) { if (hashmap.has(pB)) return pB pB = pB.next } }
方法 3：双指针
如果链表没有交点
两个链表长度一样，第一次遍历结束后 pA 和 pB 都是 null，结束遍历 两个链表长度不一样，两次遍历结束后 pA 和 pB 都是 null，结束遍历
复杂度
时间复杂度：O(M + N) , M, N 分别为两个链表的长度。 空间复杂度：O(1)。
/** * 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) { if (!headA || !headB) return null let pA = headA, pB = headB while (pA !== pB) { pA = pA === null ? headB : pA.next pB = pB === null ? headA : pB.next } return pA }
206.反转链表
var reverseList = function (head) { let prev = null cur = head while (cur) { const next = cur.next cur.next = prev prev = cur cur = next } return prev }
方案 2
var reverseList = function (head) { let prev = null cur = head while (cur) { const next = cur.next cur.next = prev prev = cur cur = next } return prev }
234.回文链表
https://leetcode-cn.com/problems/palindrome-linked-list
const isPalindrome = (head) => { const vals = [] while (head) { // 丢进数组里 vals.push(head.val) head = head.next } let start = 0, end = vals.length - 1 // 双指针 while (start < end) { if (vals[start] != vals[end]) { // 理应相同，如果不同，不是回文 return false } start++ end-- // 双指针移动 } return true // 循环结束也没有返回false，说明是回文 }
543.二叉树的直径
https://leetcode-cn.com/problems/diameter-of-binary-tree
方法 1
var diameterOfBinaryTree = function (root) { // 默认为1是因为默认了根节点自身的路径长度 let ans = 1 function depth(rootNode) { if (!rootNode) { // 如果不存在根节点，则深度为0 return 0 } // 递归，获取左子树的深度 let left = depth(rootNode.left) // 递归，获取右子树的深度 let right = depth(rootNode.right) /* 关键点1 L+R+1的公式是如何而来？ 等同于：左子树深度(节点个数) + 右子树深度（节点个数） + 1个根节点 便是这株二叉树从最左侧叶子节点到最右侧叶子节点的最长路径 类似于平衡二叉树的最小值节点到最大值节点的最长路径 之所以+1是因为需要经过根节点 */ // 获取该树的最长路径和现有最长路径中最大的那个 ans = Math.max(ans, left + right + 1) /* 关键点2 已知根节点的左右子树的深度， 则，左右子树深度的最大值 + 1， 便是以根节点为数的最大深度*/ return Math.max(left, right) + 1 } depth(root) // 由于depth函数中已经默认加上数节点的自身根节点路径了，故此处需减1 return ans - 1 }
方法 2
function height(node) { //求树高 if (!node) return 0 return 1 + Math.max(height(node.left), height(node.right)) } var diameterOfBinaryTree = function (root) { if (!root) return 0 let tempH = height(root.left) + height(root.right) return Math.max( tempH, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right) ) }
617.合并二叉树
https://leetcode-cn.com/problems/merge-two-binary-trees/
var mergeTrees = function (root1, root2) { if (root1 == null && root2) { return root2 } else if (root2 == null && root1) { return root1 } else if (root1 && root2) { root1.val = root1.val + root2.val //递归合并每一个节点 root1.left = mergeTrees(root1.left, root2.left) root1.right = mergeTrees(root1.right, root2.right) } return root1 }
注：部分题解参考LeetCode最佳题解，有需要的同学可以自行去LeetCode官网查看。
