LeetCode 160. Intersection of Two Linked Lists

题目链接)

题意:

要求你用$O(n)$的时间复杂度、$O(1)$的空间复杂度找到两个链表的交点,若无交点返回None

思路:

一道百度经典的面试题。

最简单的方法就是暴力,时间复杂度$O(mn)$、空间复杂度$O(1)$
其次可以使用hash table,但是这样时间复杂度为$O(n + m)$,空间复杂度却为$O(n)$ or $O(m)$.
这题可以使用双指针来很好的解决。初始pA指向headA,pB指向headB;两个双指针每次都走一步。若pA先到达A的尾部则令其指向B并从头继续走;若pB先到达尾部则指向A继续走。可以证明,若二者存在交点则一定会在交点处相遇,且若无交点最后会同时指向None(pA指向B的尾部,pB指向A的尾部)。

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def getIntersectionNode(self, headA, headB):
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA is not None else headB
pB = pB.next if pB is not None else headA
return pA

-------------本文结束感谢您的阅读-------------


本文标题:LeetCode 160. Intersection of Two Linked Lists

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2020年01月31日 - 20:01

最后更新:2020年01月31日 - 20:01

原始链接:https://statusrank.xyz/articles/fad8ecc0.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: