首页 题目记录 字节校园

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

学习计划链接：冲刺春招 - 精选笔面试 66 题大通关

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

昨日题目链接：冲刺春招 - 精选笔面试 66 题大通关 day16

# 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
};