[LeetCode BY Python]160. Intersection of Two Linked Lists

最新推荐文章于 2021-04-01 01:03:13 发布

原创最新推荐文章于 2021-04-01 01:03:13 发布 · 310 阅读

0 ·

CC 4.0 BY-SA版权

LeetCode[python] 专栏收录该内容

47 篇文章

订阅专栏

本文介绍了一种使用字典来解决两个单链表交点查找问题的方法。通过遍历第一个链表并记录节点值，再遍历第二个链表检查是否与已记录节点值相同，从而找到交点。

题目：

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

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

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.

解释：

我是利用字典遍历headA，然后当headB中出现与A中一样就返回

代码：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        else:
            pthis = {}
            i = headA
            while i:
                pthis[i.val] = 1
                i = i.next
            j = headB
            while j:
                if j.val in pthis:
                    return j
                else:
                    j = j.next
            return None