链表

206 反转链表

问题：https://leetcode-cn.com/problems/reverse-linked-list/description/

解：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  let cur = head
  let prev = null
  while (cur !== null) {
    let next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
};

24 两两交换链表中的节点

问题：https://leetcode-cn.com/problems/swap-nodes-in-pairs/description/

解：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  // 还不知道dummyHead的时候写的版本
  // let cur = head, prev = null
  // while (cur !== null && cur.next !== null) {
  //   if (prev === null) {
  //     head = cur.next
  //   } else {
  //     prev.next = cur.next
  //   }
  //   prev = cur
  //   let temp = cur.next.next
  //   cur.next.next = cur
  //   cur.next = temp
  //   cur = temp
  // }
  // return head
  
  // dummyHead
  const dummyHead = new ListNode()
  let cur = head, prev = dummyHead
  dummyHead.next = head
  while (cur !== null && cur.next !== null) {
    prev.next = cur.next
    prev = cur
    const temp = cur.next.next
    cur.next.next = cur
    cur.next = temp
    cur = temp
  }
  return dummyHead.next
};

141 环形链表

问题：https://leetcode-cn.com/problems/linked-list-cycle/

解：

/**
 * @param {ListNode} head
 * @return {boolean}
 */

// 1. 使用Set，时间复杂度O(n)，空间复杂度O(n)
var hasCycle = function(head) {
  const set = new Map()
  let cur = head
  while (cur !== null) {
    if (set.has(cur)) {
      return true
    }
    set.add(cur)
    cur = cur.next
  }
  return false
};

// 2. 快慢指针 - 快慢相遇，则存在环
// 时间复杂度O(n), 空间复杂度O(1)
var hasCycle = function(head) {
  let slow = head, fast = head
  while (slow && fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
};

142 环形链表2

题目：https://leetcode-cn.com/problems/linked-list-cycle-ii/

解：

// 1. 使用Set，与141相同，此处略过。
// 2. 快慢指针，类似141.

25 K个一组反转链表

题目：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

栈

20 有效的括号

题目：

https://leetcode-cn.com/problems/valid-parentheses/

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  const map = {
    ')': '(',
    '}': '{',
    ']': '['
  }
  const stack = []
  for (let i = 0; i < s.length; i++) {
    if (['}', ')', ']'].includes(s[i])) {
      if (stack.pop() !== map[s[i]]) {
        return false
      }
    } else {
      stack.push(s[i])
    }
  }
  return !stack.length
};

树

144 二叉树的前序遍历

根节点 - 左子树 - 右子树

题目：

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  let res = []
  if (root !== null) res.push(root.val)
  if (root.left !== null) res = [...res, ...preorderTraversal(root.left)]
  if (root.right !== null) res = [...res, ...preorderTraversal(root.right)]
  return res
};

145 二叉树的后序遍历

左子树 - 右子树 - 根节点

题目：

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
  let res = []
  if (root && root.left !== null) {
    res = [...res, ...postorderTraversal(root.left)]
  }
  if (root && root.right !== null) {
    res = [...res, ...postorderTraversal(root.right)]
  }
  if (root !== undefined && root !== null) {
    res.push(root.val)
  }
  return res
};

94 二叉树的中序遍历

左子树 - 根节点 - 右子树

题：

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let res = []
  if (root && root.left !== null) {
    res = [...res, ...inorderTraversal(root.left)]
  }
  if (root !== undefined && root !== null) {
    res.push(root.val)
  }
  if (root && root.right !== null) {
    res = [...res, ...inorderTraversal(root.right)]
  }
  return res
};

1361. 验证二叉树

题：

https://leetcode-cn.com/problems/validate-binary-tree-nodes

var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
  let seen = new Set()
  // 先遍历，找到入度为0的节点。
  for (let i = 0; i < n; i++) {
    if (leftChild[i] !== -1) {
      seen.add(leftChild[i])
    }
    if (rightChild[i] !== -1) {
      seen.add(rightChild[i])
    }
  }
  let k = -1
  for (let i = 0; i < n; i++) {
    if (!seen.has(i)) {
      k = i
    }
  }
  // 然后遍历树，判断联通性。
  let s = new Set()
  try {
    traverse(k, leftChild, rightChild, s)
  } catch (error) {
    console.log('环')
    return false
  }
  console.log(s)
  if (s.size === n) {
    return true
  } else {
    return false
  }

  function traverse (n, leftChild, rightChild, result) {
    if (leftChild[n] !== -1) {
      traverse(leftChild[n], leftChild, rightChild, result)
    }
    if (rightChild[n] !== -1) {
      traverse(rightChild[n], leftChild, rightChild, result)
    }
    // 注意这里的判断
    if (result.has(n)) {
      throw 'cicular'
    }
    result.add(n)
  }
};

236 二叉树的最近公共祖先

题：

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  if (root === null) return null
  if (root === p || root === q) return root
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)
  if (left && right) {
    return root
  } else if (left === null) {
    return right
  } else {
    return left
  }
};

misc

15 三数之和

双指针法：

先排序，再单循环，每个循环使用头尾两个指针判断三数之和是否为0并移动指针。

难点在于如何排除重复的解：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  if (nums.length < 3) {
    return []
  }
  nums.sort((a, b) => {
    return a - b
  })
  const result = []
  for (let i = 0; i < nums.length; i++) {    
    let L = i + 1
    let R = nums.length - 1
    // 从第一个数排除重复解
    if (nums[i] === nums[i - 1]) continue

    while (L < R) {
      let sum = nums[i] + nums[L] + nums[R]
      if (sum === 0) {
        const tempRes = [nums[i], nums[L], nums[R]]
        result.push(tempRes)
        // 从第二、三个数排除重复解
        while(L < R && nums[R] === nums[R - 1]) R--
        while(L < R && nums[L] === nums[L + 1]) L++
        L++
        continue
      } else if (sum > 0) {
        R--
      } else {
        L++
      }
    }
  }
  return result
};