【剑指Offer刷题系列】两个单链表相交的起始节点

问题描述

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

图示两个链表在节点 c1 开始相交：

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

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

自定义评测：

• 评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：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，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

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

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O ( m + n ) O(m + n) O(m+n) 、仅用 O ( 1 ) O(1) O(1)内存的解决方案。

Leetcode链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

思路解析

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

1. 单链表的特性：链表从头到尾只能沿着 next 指针单向遍历。
2. 内存地址是否重合：两个链表相交意味着它们在某一节点之后共用同一段内存地址。
3. 不改变原始链表结构：要求不能破坏链表结构。

思路一：暴力法（不推荐）
对于每个链表 listA 的节点，遍历链表 listB，检查是否存在一个节点是内存地址相同的（即节点相交）。

缺点：

• 时间复杂度 O ( m × n ) O(m \times n) O(m×n)，效率低下。
• 空间复杂度 O ( 1 ) O(1) O(1)，不需要额外空间。

思路二：哈希表法
使用一个哈希表记录链表 listA 的所有节点，然后遍历链表 listB，判断节点是否已经存在于哈希表中。

步骤：

1. 遍历链表 listA，将每个节点加入哈希表。
2. 遍历链表 listB，判断当前节点是否在哈希表中。
3. 如果找到，返回该节点；否则继续。
4. 若遍历结束没有找到相交节点，返回 null。

复杂度：

• 时间复杂度： O ( m + n ) O(m + n) O(m+n)，一次遍历链表 A 和 B。
• 空间复杂度： O ( m ) O(m) O(m)，需要额外存储链表 A 的节点。

思路三：双指针法（推荐）
通过双指针法可以实现时间复杂度 O ( m + n ) O(m + n) O(m+n)，空间复杂度 O ( 1 ) O(1) O(1) 的解法。

核心思想：
两个指针分别从链表 listA 和 listB 的头节点出发，逐个比较节点。
当一个指针到达链表尾部时，跳到另一个链表的头节点继续遍历。这样两指针总会同时到达相交点或都为 null。

步骤：

1. 创建两个指针 pA 和 pB，分别指向链表 listA 和 listB 的头节点。
2. 遍历两个链表：
   • 如果 pA 到达链表尾部，则指向链表 listB 的头节点。
   • 如果 pB 到达链表尾部，则指向链表 listA 的头节点。
   • 如果 pA == pB，即找到相交节点，返回该节点。
3. 如果遍历结束且没有找到相交节点，则返回 null。

优点：
通过两次遍历让两个指针同步到相交点（或 null），不需要额外的空间。

代码实现

以下是使用 双指针法 的代码实现：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA, headB):
        """
        找出两个链表的相交起始节点
        :param headA: ListNode, 第一个链表的头节点
        :param headB: ListNode, 第二个链表的头节点
        :return: ListNode, 相交起始节点或 None
        """
        if not headA or not headB:
            return None
        
        # 初始化两个指针
        pA, pB = headA, headB
        
        # 遍历两个链表
        while pA != pB:
            # 如果 pA 到达尾部，则跳到 headB，否则继续向下
            pA = pA.next if pA else headB
            # 如果 pB 到达尾部，则跳到 headA，否则继续向下
            pB = pB.next if pB else headA
        
        # 返回相交节点或 None
        return pA

测试代码

# 辅助函数：根据列表构建链表
def build_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# 辅助函数：打印链表
def print_linked_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    print(" -> ".join(map(str, result)) if result else "空链表")

# 测试函数
def test():
    solution = Solution()
    
    # 测试 1：链表相交
    print("测试 1：")
    # 构建链表 1
    headA = build_linked_list([4, 1])
    headB = build_linked_list([5, 6, 1])
    intersection = build_linked_list([8, 4, 5])
    # 连接链表相交部分
    headA.next.next = intersection
    headB.next.next.next = intersection
    result = solution.getIntersectionNode(headA, headB)
    print(result.val if result else "无交点")  # 输出：8

    # 测试 2：链表不相交
    print("\n测试 2：")
    headA = build_linked_list([2, 6, 4])
    headB = build_linked_list([1, 5])
    result = solution.getIntersectionNode(headA, headB)
    print(result.val if result else "无交点")  # 输出：无交点

    # 测试 3：一个链表为空
    print("\n测试 3：")
    headA = build_linked_list([])
    headB = build_linked_list([1, 2, 3])
    result = solution.getIntersectionNode(headA, headB)
    print(result.val if result else "无交点")  # 输出：无交点

# 执行测试
test()

复杂度分析

1. 时间复杂度：

   • 每个指针最多遍历两个链表一次，时间复杂度为 O ( m + n ) O(m + n) O(m+n)。

2. 空间复杂度：

   • 双指针法不需要额外空间，空间复杂度为 O ( 1 ) O(1) O(1)。

输出示例

运行上述代码后，输出结果如下：

测试 1：
8

测试 2：
无交点

测试 3：
无交点