【Leetcode刷题Python】106.相交链表

简介: 采用双指针法来找出两个链表的相交起始节点,并详细解释了算法的时间和空间复杂度。

1 题目

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
1.png

注意:

如果两个链表没有交点,返回 null。
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

2 图解

考虑构建两个节点指针 A​ , B 分别指向两链表头节点 headA , headB ,做如下操作:
指针 A 先遍历完链表 headA ,再开始遍历链表 headB ,当走到 node 时,共走步数为:
a + (b - c)
a+(b−c)

指针 B 先遍历完链表 headB ,再开始遍历链表 headA ,当走到 node 时,共走步数为:
b + (a - c)
b+(a−c)

如下式所示,此时指针 A , B 重合,并有两种情况:

a + (b - c) = b + (a - c)
a+(b−c)=b+(a−c)

若两链表 有 公共尾部 (即 c > 0c>0 ) :指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c = 0c=0 ) :指针 A , B 同时指向 nullnull 。
因此返回 A 即可。
如下图所示,为 a = 5a=5 , b = 3b=3 , c = 2c=2 示例的算法执行过程。

思路来源链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
(1)第一步
2.png

(2)第二步
3.png

(3)第三步
4.png

(4)第四步
B走到了null,则指针接下来将会指向HeadA
5.png

(5)第五步
B指针指向HeadA
6.png

(6)第六步
A走到了null,则指针接下来将会指向HeadB
7.png

(7)第七步
8.png

(8)第八步
指针A等于指针B,此时返回指针A即可。如果两条链没有相交,一定会在Null相交,返回的是NULL
9.png

3 Python实现

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        '''
        方法一:双指针法,图解参考https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
        时间复杂度:O(m+n)O(m+n),其中 mm 和 nn 是分别是链表 \textit{headA}headA 和 \textit{headB}headB 的长度。两个指针同时遍历两个链表,每个指针遍历两个链表各一次。

        空间复杂度:O(1)O(1)。
        '''
        A,B = headA,headB
        while(A!=B):
            A = A.next if A else headB
            B = B.next if B else headA
        return A

注意以上代码的用法
A if case else B表示如果case为真,则返回 A,否则返回 B。

目录
相关文章
|
15天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
30 1
|
21天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
43 0
Leetcode第21题(合并两个有序链表)
|
1天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
5 1
|
19天前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
15 1
|
21天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
13 0
LeetCode第二十四题(两两交换链表中的节点)
|
21天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
21天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
53 0
|
22天前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
18 0
|
22天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
13 0
|
22天前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0