day19：160. 相交链表、143. 重排链表、142. 环形链表 II

day19题目：160. 相交链表、143. 重排链表、142. 环形链表 II

今日知识点：链表、递归、双指针，难度为简单、中等、中等

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

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

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交 ：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

• listA - 第一个链表

• listB - 第二个链表

• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出： Intersected at '8'
解释： 相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入： intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出： Intersected at '2'
解释： 相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入： intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出： null
解释： 从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m

• listB 中节点数目为 n

• 1 <= m, n <= 3 * 10^4

• 1 <= Node.val <= 10^5

• 0 <= skipA <= m

• 0 <= skipB <= n

• 如果 listA 和 listB 没有交点，intersectVal 为 0

• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

思路

双指针，利用 prea 和 preb 作为a和b的前一个结点，当 prea === preb 时说明这当前节点上一个节点都是同一个结点

代码

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

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null
    let [prea, preb] = [headA, headB]
    while(prea !== preb) {
        prea = prea.next
        preb = preb.next
        if(prea === preb) return prea
        if(!prea) prea = headB
        if(!preb) preb = headA
    }
    return prea
};

143. 重排链表

给定一个单链表 L **的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

示例 2：

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

提示：

• 链表的长度范围为 [1, 5 * 10^4]

• 1 <= node.val <= 1000

思路

• 若没有结点或只有一两个结点，则无需操作。

• 每次将最后一个结点 nowv 接在头结点 head 后面

• 然后将倒数第二个结点 prev 置为最后一个节点

• 再对递归的原本的第三个结点 nowv.next 以及之后的链表进行该操作

代码

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    if(!head || !head.next) return;
    let [prev, nowv] = [null, head];
    while(nowv.next) {
        prev = nowv
        nowv = nowv.next
    }
    if(!prev || prev === head)  return
    prev.next = null
    nowv.next = head.next
    head.next = nowv
    reorderList(nowv.next)
};

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围在范围 [0, 10^4] 内

• -10^5 <= Node.val <= 10^5

• pos 的值为 -1 或者链表中的一个有效索引

进阶： 你是否可以使用 O(1) 空间解决此题？

思路

环形链表在冲刺春招-精选笔面试 66 题大通关 day17中有做过，主要思想是快慢指针，快指针一次走两步，慢指针一次走一步，若有环则一定会遇上，否则没有环。

而这里需要返回入环处的结点，那么，当快指针 fast 等于慢指针 slow 时，设置一个新的指针 ptr 跟着 slow 一块走，最终 ptr 和 slow 就会在入环结点相遇。 推导如下，直接看官方的吧：

如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，假设 fast 指针已经走完了环的 n 圈，则 fast 走过的总距离为 a+n(b+c)+b 化简得 a+(n+1)b+nc。 由于快指针每次都比慢指针多走一步，故 fast 走过的距离是 slow 的两倍，而 slow 走过的总距离为 a+b，所以有 a+(n+1)b+nc = 2(a+b)，解得 a = c+(n-1)(b+c)

• 也就是说，从相遇点到入环点的距离 c 加上n-1圈环长（b+c），恰好等于链表头部到入环点的距离 a

• 因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，ptr 指向链表头部。随后，ptr 和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let [slow, fast] = [head, head];
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if(slow === fast) break
    }
    if(!fast || !fast.next) return null
    let p = head
    while(p !== slow) {
        p = p.next
        slow = slow.next
    }
    return p
};