题目描述

给定两个链表，请找它们的交汇点。

注意：

• 如果两个链表不相交，则返回 null；
• 在函数结束时，两个链表必须保持原来的结构；
• 链表中不存在环；
• 你的代码需要的时间复杂度是 $O(n)$，额外的空间复杂度是 $O(1)$；

样例

给定如下两个链表：

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗            
B:     b1 → b2 → b3

则交汇点是 c1。

算法

(链表，指针扫描) $O(n)$

这题的思路很巧妙，我们先给出做法，再介绍原理。

算法步骤：

1. 用两个指针分别从两个链表头部开始扫描，每次分别走一步；
2. 如果指针走到null，则从另一个链表头部开始走；
3. 当两个指针相同时，
   • 如果指针不是null，则指针位置就是相遇点；
   • 如果指针是 null，则两个链表不相交；

此题我们画图讲解，一目了然：

$1$. 两个链表不相交：

$a,b$ 分别代表两个链表的长度，则两个指针分别走 $a+b$ 步后都变成 null。

$2$. 两个链表相交：

则两个指针分别走 $a+b+c$ 步后在两链表交汇处相遇。

时间复杂度分析：每个指针走的长度不大于两个链表的总长度，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA, *q = headB;
        while (p != q)
        {
            if (p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};