Leetcode题160、相交链表（Python题解）

问题：

题目来源：力扣（LeetCode）

leetcode160.相交链表

难度：简单

分析： 这竟然是到简单题emm，code确实挺简单的，但是思路不是一下子就能想到的啊。 思路一、哈希。将链表1的的节点存下来，依次检查链表2中是否有节点在链表1中。但这种方法无法满足O（1）的空间复杂度。 思路二、拼接链表法。见下面的图。

解决方法： 1：哈希

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: A = set() cur1 = headA cur2 = headB while cur1: A.add(cur1) cur1 = cur1.next while cur2: if cur2 in A: return cur2 cur2 = cur2.next return None

2：拼接链表法 见下图，当链表1走到尾部的时候，继续从链表2的头部开始走，即路径为a-c-b-c。当链表2走到尾部的时候，继续从链表21的头部开始走，即路径为b-c-a-c。 a + c + b + c = b + c + a + c.,两个链表必然会在c开始的地方相遇，也就是两条链表开始相交的地方。

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: ha, hb = headA, headB while ha != hb: ha = ha.next if ha else headB hb = hb.next if hb else headA return ha

图片来源链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/jiao-ni-yong-lang-man-de-fang-shi-zhao-dao-liang-2/