链表-计算两个链表是否相交

发表于 分类于

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

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

img

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

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

那么我们的算法应该返回 c1 这个节点。

这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

img

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

**解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1**。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

img

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。

按照这个思路，可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 判断两个链表是否相交
 * @param headA
 * @param headB
 * @return
 */
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //p1指向A链表头结点,p2指向B链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1!=p2){
        //p1走一步，如果走到A链表末尾，则转到B链表继续走
        if(p1==null){
            p1 = headB;
        }else{
            p1 = p1.next;
        }
        //p2走一步，如果走到B链表末尾，则转到B链表继续走
        if(p2==null){
            p2 = headA;
        }else{
            p2 = p2.next;
        }
    }
    return p1;
}