二叉树的层次遍历、合并有序链表、链表中环的入口节点

二叉树的层次遍历

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是

[
[3],
[9,20],
[15,7]
]

示例 1
输入

{1,2}

输出

[[1],[2]]

示例 2
输入

{1,2,3,4,#,#,5}

输出

[[1],[2,3],[4,5]]

思路

使用一个数组存储当前层的所有节点，遍历拿到值以后再加入结果数组中，同时把它们的左右节点加入队列数组中。

解答

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
 *
 * @param root TreeNode类
 * @return int整型二维数组
 */
function levelOrder(root) {
  // write code here
  if (!root) return [];
  const res = [];
  const queue = [];
  queue.unshift(root);
  while (queue.length) {
    let tmp = queue.splice(0, queue.length);
    let tmp2 = [];
    while (tmp.length) {
      let node = tmp.shift();
      tmp2.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(tmp2);
  }
  return res;
}
module.exports = {
  levelOrder: levelOrder,
};

合并有序链表

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。

示例 1
输入

{1},{}

输出

{1}

示例 2
输入

{1},{1}

输出

{1,1}

思路

两个指针指向链表头，不断比较值，加入结果列表，并下移指针。其中一条遍历完之后，将剩下一条都放入结果链表即可。

解答

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param l1 ListNode类
 * @param l2 ListNode类
 * @return ListNode类
 */
function mergeTwoLists(l1, l2) {
  // write code here
  let tmp = new ListNode(null);
  const res = tmp;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tmp.next = new ListNode(l1.val);
      l1 = l1.next;
    } else {
      tmp.next = new ListNode(l2.val);
      l2 = l2.next;
    }
    tmp = tmp.next;
  }
  while (l1) {
    tmp.next = new ListNode(l1.val);
    l1 = l1.next;
    tmp = tmp.next;
  }
  while (l2) {
    tmp.next = new ListNode(l2.val);
    l2 = l2.next;
    tmp = tmp.next;
  }
  return res.next;
}
module.exports = {
  mergeTwoLists: mergeTwoLists,
};

链表中环的入口节点

对于一个给定的链表，返回环的入口节点，如果没有环，返回 null
拓展：
你能给出不利用额外空间的解法么？

思路

添加 isVisit

可以取巧给每个节点加上一个属性判断是否遍历过，判断后就可以再环入口节点时返回节点。

快慢指针

快慢指针相遇只能判断是否有环。

串长 a + n，其中 n 为循环，当 a + b 步的慢指针与走了 2*(a+b)步的快指针相遇时，快指针已经走过了 k 圈，k>=1。
即**a + b + k * n = 2 _ (a+b)**，求 a，得到 a = k _ n - b。
也就是头结点从 X 走 a 步，等于 Z 位置上的指针再走 k 圈减去 b 的长度，相遇于 Y 点，即环的入口。

解答

添加 isVisit

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @return ListNode类
 */
function detectCycle(head) {
  // write code here
  while (head) {
    if (head.isVisit) return head;
    head.isVisit = true;
    head = head.next;
  }
  return null;
}
module.exports = {
  detectCycle: detectCycle,
};

快慢指针

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @return ListNode类
 */
function detectCycle(head) {
  // write code here
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      let tmp = head;
      while (tmp !== fast) {
        tmp = tmp.next;
        fast = fast.next;
      }
      return tmp;
    }
  }
  return null;
}
module.exports = {
  detectCycle: detectCycle,
};