4.28

206.反转链表

/**
 * 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}
 */
// 核心思路以单个节点操作，缓存下个，指针指向pre，缓存当前节点给下个用
var reverseList = function(head) {
    let pre = null
    let curr = head
    while(curr) {
        let next = curr.next
        curr.next = pre
        pre = curr
        curr = next
    }
    // 一定返回的是pre因为构成了新链表
    return pre
};

112 路径总和

/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
 // 回忆下dfs、bfs
 // bfs层次遍历：每个子节点放到数组里，处理每个节点后，pop。然后while结束
 // dfs递归找下个节点，先找终止条件。然后执行函数，再递归
 // 本题思路直接累减
var hasPathSum = function(root, targetSum) {
    if (!root) {
        return false;
    }
    if (!root.left && !root.right && root.val === targetSum) {
        return true;
    }
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};

102. 二叉树的层序遍历

大思路理解，每层维护一个q，然后while循环，但是里面细节处理不太明白

/**
 * 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 levelOrder = function(root) {
    let q = [root]
    let res = []
    if (!root) return []
    while(q.length) {
        const currentSize = q.length
        res.push([])
        for(let j = 1; j <= currentSize; ++j) {
            let tmp = q.shift()
            res[res.length - 1].push(tmp.val)
            if (tmp.left) {
                q.push(tmp.left)
            } 
            if (tmp.right) {
                q.push(tmp.right)
            }
        }
    }
    return res
};

15. 三数之和
题解
https://leetcode-cn.com/problems/3sum/solution/by-veneno-o-xmwf/

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 // 先sort升序，
 // 第一层循环，找剩余的target
 // 开始双指针
 // 如果重复就跳过
var threeSum = function(nums) {
    let list = nums.sort((a, b) => a - b)
    let res = []
    // 为什么是-2？
    for(let i = 0; i < list.length - 2; i++) {
        // 重复检测
        if (list[i] === list[i - 1]) continue
        const target = -list[i]
        let j = i + 1
        let k = list.length - 1
        while(j < k) {
            // 重复检测
            // 这里两个重复不明白
            if (j > i + 1 && list[j] === list[j - 1]) {
                j++
                continue
            }
            if (list[k] === list[k + 1]) {
                k--
                continue
            }
            if (list[j] + list[k] === target) {
                res.push([list[i], list[j], list[k]])
                j++
                k--
            } else if (list[j] + list[k] < target) {
                j++
            } else {
                k--
            }
        }
        return res
    }
};