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)  内存的解决方案?

# 思路

双指针,利用 preapreb 作为 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 一块走,最终 ptrslow 就会在入环结点相遇。
推导如下,直接看官方的吧:

如下图所示,设链表中环外部分的长度为 aslow  指针进入环后,又走了  b  的距离与  fast  相遇。此时,假设 fast  指针已经走完了环的  n  圈,则 fast 走过的总距离为 a+n(b+c)+b 化简得 a+(n+1)b+nc
fig1

由于快指针每次都比慢指针多走一步,故 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
  • 因此,当发现  slowfast 相遇时,我们再额外使用一个指针  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
};