160. 相交链表

题目链接：160. 相交链表

题目描述

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

核心思考：双指针消除长度差

这道题最直观的难点在于，两个链表的长度可能不一致，因此我们无法让两个指针从头开始同步走到相交点。

如果能想办法消除长度差，让两个指针处于同一起跑线上，问题就迎刃而解了。如何巧妙地做到这一点呢？我们可以让两个指针各自走过对方走过的路：

1. 逻辑上的路径拼接：假设链表 A 的独立长度为 a，链表 B 的独立长度为 b，两者相交的公共部分长度为 c。
2. 指针 p1 从 headA 出发，走完链表 A 后，立刻跳转到 headB 的开头继续走。它走过的总路程将是：a + c + b。
3. 指针 p2 从 headB 出发，走完链表 B 后，立刻跳转到 headA 的开头继续走。它走过的总路程将是：b + c + a。
4. 殊途同归：显而易见，a + c + b = b + c + a。无论两条链表原本有多长，只要按照这种方案走，两个指针最终一定会同时到达相交节点。

那如果两个链表压根不相交呢？同理，当指针分别走过 a + b 和 b + a 的距离后，它们会同时指向各自尽头的空指针 None，也就是在末尾相遇并双双退出。

解题思路 (Python)

我们只需要用 while p1 != p2 作为跳出条件，一旦某个指针走到尽头，就让它从另一个链表的头部重新开始。

# 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) -> Optional[ListNode]:
        p1,p2 = headA,headB
        while p1 != p2:
            if p1 == None:
                p1 = headB
            else:
                p1 = p1.next
            if p2 == None:
                p2 = headA
            else:
                p2 = p2.next
        return p1

复杂度分析

• 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别为两个链表的长度。两个指针最差情况下各自遍历一遍链表 A 和链表 B，总体执行次数线性相关。
• 空间复杂度：$O(1)$。算法只分配了两个额外的指针指向已有节点，没有任何多余的内存开辟。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

import sys

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    p1,p2 = headA,headB
            while p1 != p2:
                if p1 == None:
                    p1 = headB
                else:
                    p1 = p1.next
                if p2 == None:
                    p2 = headA
                else:
                    p2 = p2.next
            return p1

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.getIntersectionNode(nums)
    for v in result:\n        print(v, end=' ')\n    print()

if __name__ == "__main__":
    main()

运行示例：

echo "2 -1 3 4 -5" | python solution.py