您现在的位置:首页 > >

【LeetCode】160. 两个链表的交集

发布时间:

问题描述

Write a program to find the node at which the intersection of two singly linked lists begins.


Notes:


If the two linked lists have no intersection at all, return?null.The linked lists must retain their original structure after the function returns.You may assume there are no cycles anywhere in the entire linked structure.Your code should preferably run in O(n) time and use only O(1) memory.

编写一个程序,找出两个单链表相交的起始点。


注:


如果两个链表没有交集,则返回null。函数返回后,链表必须保持原来的结构。你可以假设在整个链接结构的任何地方都没有环。你的代码最好在O(n)时间内运行,并且只使用O(1)内存。

例如,下面两个链表:



从节点 c1 开始有交集。


?


Python 实现

实现一:先将一个链表的每个结点存到一个列表中,然后依次判断另一个链表的每一个结点是否在列表中出现。这个思路很直接,但是考虑到列表 in 的操作有较大的时间复杂度,所以这个方法其实不是特别理想。


class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""

existed = []
while headA != None:
existed.append(headA)
headA = headA.next
while headB != None:
if headB in existed:
return headB
else:
headB = headB.next
return None

实现二:考虑到如果两个链表有交集的话,它们末尾的结点一定是相同的。因此从末尾开始比较是一个更有效率的方法。我们可以分别将两个链表转换成列表,然后依次弹出末尾的元素,比较是否相等,一旦出现相同结点,说明两个链表有交集,最晚出现的相同结点,则为交集出现的起点。


class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""

ret = None
a = []
b = []
while headA != None:
a.append(headA)
headA = headA.next
while headB != None:
b.append(headB)
headB = headB.next

while a and b:
a_node = a.pop()
b_node = b.pop()

if a_node == b_node:
ret = a_node
else:
return ret
return ret

实现三:直接比较两个链表的对应位置的结点是否相同,如果没有找到相同的结点,其中一个链表遍历完成后,其指针指向另一个链表的头结点并开始遍历该链表。由于在第一轮遍历时,遍历较短的链表会更快结束,因此当另一个链表遍历完后,该指针在新链表中已经将较长链表多出来的前面部分遍历完。也就是说,当两个链表都进入第二轮遍历时,他们距离链表末尾的长度都一样。实际上该方法属于第二种实现的另外一种模式。


class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""

if headA == None or headB == None:
return None
a, b = headA, headB

while a != b:
if a == None:
a = headB
else:
a = a.next

if b == None:
b = headA
else:
b = b.next

return a

链接:https://leetcode.com/problems/intersection-of-two-linked-lists/


热文推荐
猜你喜欢
友情链接: 大学学习资料 人文社科 经营营销资料 工程资料大全 IT文档 自然科学