【160】相交链表
又是要求要空间复杂度为O(1)
第一种解法：时间复杂度和空间复杂度都是O(n)
给headA循环添加一个标记，然后去循环headB 判断headB是否有被标记过的节点，如果有则为相交节点，没有则返回NULL
function getIntersectionNode(headA, headB) { while(headA) { headA.flag = true headA = headA.next } while(headB) { if (headB.flag) return headB headB = headB.next } return null};第二种解法：本题主要是考察双指针的用法吧。如果A、B相交，那么A、B自相交节点往后的链表是一致的。
我们可以尝试消除 A、B 链表的长度差，从数量相等的位置开始，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。
时间复杂度：O(n)
空间复杂度：O(1)
var getIntersectionNode = function(headA, headB) { // 清除高度差 let pA = headA, pB = headB while(pA || pB) { if(pA === pB) return pA pA = pA === null ? headB : pA.next pB = pB === null ? headA : pB.next } return null};【206】反转一个单链表
要求用递归和迭代两种方法来处理
第一种方法迭代法：
时间复杂度：O(n)
空间复杂度：O(1)
function reverseList(head) { if(!head || !head.next) return head var prev = null, curr = head while(curr) { // 用于临时存储 curr 后继节点 var next = curr.next // 反转 curr 的后继指针 curr.next = prev // 变更prev、curr // 待反转节点指向下一个节点 prev = curr curr = next } head = prev return head};第二种方法：递归法
时间复杂度：O(n)
空间复杂度：O(n)
function reverseList(head) { if(!head || !head.next) return head var next = head.next // 递归反转 var reverseHead = reverseList(next) // 变更指针 next.next = head head.next = null return reverseHead};[217]给定一个整数数组，判断是否存在重复元素
本题主要考察的应该是Set吧
方法一：
最开始想了一个最笨的方法，暴力法，两层循环挨个比较，超级没有技术含量，其实还可以先排序，但也不是最简单的解法。
/** * @param {number[]} nums * @return {boolean} */var containsDuplicate = function(nums) { for(var i = 0; i < nums.length; i++){ for(var j = 0; j < nums.length; j++){ if(nums[i] == nums[j] && i != j){ return true; } } } return false;};方法二：参考了题解用一行代码搞定
set 去重 然后比较大小
var containsDuplicate = function(nums) { return !(nums.length === new Set(nums).size);};【235】二叉搜索树的最近公共祖先：给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。
然后第一个疑问点就是对最近公共祖先的定义：百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
题解：利用二叉搜索树的特点。大小规律可以采用递归法解题
var lowestCommonAncestor = function(root, p, q) { if(root == null){return root} if(p.val < root.val && root.val > q.val){ return lowestCommonAncestor(root.left, p, q); } if(p.val > root.val && root.val < q.val){ return lowestCommonAncestor(root.right, p, q); } return root;};[2]两数相加
给的是两个非空的链表，且按照逆序方式存储，相加后返回一个链表也是逆序存储。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var addTwoNumbers = function(l1, l2) { var node = new ListNode(); let temp = node , sum , n = 0 while(l1 || l2){ const n1 = l1 ? l1.val : 0 const n2 = l2 ? l2.val : 0 sum = n1 + n2 + n temp.next = new ListNode( sum % 10 ) temp = temp.next n = parseInt( sum / 10 ) if(l1) l1 = l1.next if(l2) l2 = l2.next } if( n > 0 ) temp.next = new ListNode(n) return node.next};