day17 题目：141. 环形链表、236. 二叉树的最近公共祖先、92. 反转链表 II

今日知识点：快慢指针、dfs、链表，难度为简单、中等、中等

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入： head = [3,2,0,-4], pos = 1
输出： true
解释： 链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入： head = [1,2], pos = 0
输出： true
解释： 链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入： head = [1], pos = -1
输出： false
解释： 链表中没有环。

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

进阶： 你能用 O(1)（即，常量）内存解决此问题吗？

思路

快慢指针，快指针一次走两步，慢指针一次走一步，若有环则一定会遇上的，否则没有环

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  if (!head) return false;
  let [f, s] = [head, head];
  while (s.next && f.next && f.next.next) {
    f = f.next.next;
    s = s.next;
    if (f === s) return true;
  }
  return false;
};

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出： 3
解释： 节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出： 5
解释： 节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入： root = [1,2], p = 1, q = 2
输出： 1

提示：

树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

思路

先从一个节点往上走将沿途的 vis 置为 true，再从另一个结点往上走，遇到 vis 为 true 的就是最近共同祖先，返回。

代码

/**
 * 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) {
  let fa = new Map();
  let vis = new Map();
  let init = function (rt) {
    vis.set(rt.val, false);
    if (rt.left) {
      fa.set(rt.left.val, rt);
      init(rt.left);
    }
    if (rt.right) {
      fa.set(rt.right.val, rt);
      init(rt.right);
    }
  };
  fa.set(root.val, null);
  init(root);
  let ptr = p;
  while (ptr && fa.has(ptr.val)) {
    vis.set(ptr.val, true);
    ptr = fa.get(ptr.val);
  }
  ptr = q;
  while (ptr && fa.has(ptr.val)) {
    if (vis.get(ptr.val)) return ptr;
    ptr = fa.get(ptr.val);
  }
};

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入： head = [1,2,3,4,5], left = 2, right = 4
输出： [1,4,3,2,5]

示例 2：

输入： head = [5], left = 1, right = 1
输出： [5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

思路

哎，先来一个反转链表的函数，day1 的 K 组一个反转链表里边我们就写过：

var reverseList = function (s, e) {
  let prev = e.next;
  let nowv = s;
  while (prev != e) {
    let temp = nowv.next;
    nowv.next = prev;
    prev = nowv;
    nowv = temp;
  }
  return [e, s];
};

然后，当务之急是找到 left 和 right 对应的结点指针 l 和 r，以及 l 前面的 prev

翻转 let [s, e] = reverseList(l, r)，记得在之前先把 r.next 存到 temp
为了让反转后子链表能够顺利的拼回去原链表，需将反转后的 pre.next 指向s， e.next 指向 temp

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var reverseList = function (s, e) {
  let prev = e.next;
  let nowv = s;
  while (prev != e) {
    let temp = nowv.next;
    nowv.next = prev;
    prev = nowv;
    nowv = temp;
  }
  return [e, s];
};
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
  let ehead = new ListNode(0, head);
  let [prev, nowv, prel, l, r] = [ehead, head, ehead, head, head];
  for (let cnt = 1; nowv; ++cnt, nowv = nowv.next) {
    if (cnt === left) {
      prel = prev;
      l = nowv;
    }
    if (cnt === right) r = nowv;
    prev = nowv;
  }
  let temp = r.next;
  let [s, e] = reverseList(l, r);
  prel.next = s;
  e.next = temp;
  return ehead.next;
};

冲刺春招-精选笔面试66题大通关17

141. 环形链表

思路

代码

236. 二叉树的最近公共祖先

思路

代码

92. 反转链表 II

思路

代码