LeetCode刷题 NO.160 相交链表 (简单)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解析

1）判断是否有相交，可以理解为判断是否有共同元素，所以先遍历一个链表，将其元素放到一个集合中；

2）再遍历另一个，依次判断集合中是否存在，如果存在则返回节点，不存在就遍历完后返回None即可。

3）另一个方法是双指针法，设A的长度为a，B的长度为b，相交节点到尾节点之间的距离为c，则有：a+b-c = b+a-c；

4）也就是先遍历A，然后遍历B到相交节点，与先遍历B，再遍历A到相交节点的路途一样长；

5）如果不存在相交节点，此时ha和hb都会遍历完A和B最终为None。

代码示例

1、哈希存储法

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

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

执行用时：136 ms, 在所有 Python3 提交中击败了 93.81% 的用户.

2、双指针法

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