【算法】链表-20240105

发布时间:2024年01月06日

在这里插入图片描述


一、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

解题思路步骤
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

文章来源:https://blog.csdn.net/YZL40514131/article/details/135397842
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。