给你两个单链表的头节点 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

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/386