【算法】链表-20240105

在这里插入图片描述

这里写目录标题

一、LCR 023. 相交链表
二、142. 环形链表 II

一、LCR 023. 相交链表

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

在这里插入图片描述

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

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

分析
这道题比较容易想到的是，创建一个hash表，然后循环依次A，将A的所有节点添加至Hash表中。
再循环依次B，每次判断B的当前节点是否在hash表中。
代码如下：

class Solution:
    def getIntersectionNode(self,headA,headB):
        d={}
        while headA:
            d[headA]=headA
            headA=headA.next
        while headB:
            if d.get(headB):
                return headB
            headB=headB.next()
        return None

这样的思路可以通过，但是题目说了程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
hash表构造了额外的O(n)空间复杂度，那么如何来实现使用O(1)的时间复杂度完成呢？

思路：
假设相交前A链表的长度为x,B链表的长度为z
两个链表相交的点为图中的w
相交后共同的长度为y。
我们分别创建p1、p2两个指针指向A、B
当p1或者p2走到头时，则将指针重新指向另外的一个链表。
当p1、p2相等时终止，返回p1或p2就是第一个相交节点。
因为p1、p2走过的路程都是x+y+z！

在这里插入图片描述

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node_a = headA
        node_b = headB
        while node_a or node_b:
            if node_a == node_b:
                return node_a
            if node_a:
                node_a = node_a.next
            else:
                node_a = headB
            if node_b:
                node_b = node_b.next
            else:
                node_b = headA
        return

二、142. 环形链表 II

中等

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
在这里插入图片描述
思路：使用双指针法解决
本题的求解过程中，双指针会产生两次相遇
双指针的第一次相遇：
设两指针fast，slow指向链表头部head
令fast每轮走2步，slow每轮走 1步
执行以上两步后，可能出现两种结果：

第一种结果：fast指针走过链表末端，说明链表无环，此时直接返回null
如果链表存在环，则双指针一定会相遇。因为每走1轮，fast与slow的间距+1，fast一定会追上slow。

当fast == slow时，当双指针相遇时：快指针重新指向链表头部节点，slow和fast同时每轮向前走1步。
当fast指针走到f=a步时，slow指针走到s=a+b步，此时两个指针重合，并且同时指向链表环入口，返回slow指向的节点即可。

class Solution1:
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not fast and not fast.next:
                return
            fast=fast.next.next
            slow=slow.next
            if fast == slow:
                break

        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast