leetcode160-链表相交节点

1 简介

题目传送门leetcode160。

这个问题主要解决的是，找寻两个链表中相交的链表。为此，我们首先应该明白几个点：

第一，链表一旦相交，那么就不会出现再次分开的情况；
第二，长度相同的链表，如果相交，那么必定是在相对应的位置。

如果要理解以上两点内容，我们先来看看一些情形：

1.1 情形一

链表相交于c1

1.2 情形二

链表不相交

注意，情形一和情形二的区别，情形一是两个链表真正相交，情形二则是两个链表无相交点，只是有相同的值而已。

1.3 情形三

这种情形其实是不存在的，因为c3节点有两个next指针，这就解释了上面提到的第一点链表一旦相交，那么就不会出现再次分开的情况。

image.png

2 解题思路

然后我们用leetcode中提供的例子来分析一下这个题目的解题思路。链表只要相交，那么必定是下面那种情况。

2-1

我们把这个链表分成三个部分，如下图：

2-2

如上面2-2图，那么题干中链表headA和headB分别满足以下关系；

headA = x + common;
headB = y + common;

于是我们的需求就变成了求得comon链表的头节点。把两个链表相加，得到以下内容：

NewHeadA链表：headA + headB = x + common + y + common  
NewHeadB链表：headB + headA = y + common + x + common

注意(x + common + y) 和 (y + common + x)的长度肯定是一样的，那么问题就变成了同时同步地遍历NewHeadA和NewHeadB两个链表，当遇到同一个节点时那么就是common的头节点（x与y链表的节点数不一定相同）。

NewHeadA与NewHeadB链表示意图如下：

image.png

由此思路推出代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode nodeP = headA;
        ListNode nodeQ = headB;

        // 当遍历到nodeP链表尾部时，那么直接接上headB上
        // 当遍历到nodeQ链表尾部时，那么直接接上headA上
        // 以此完成两个链表相加的逻辑操作。
        while (nodeP != nodeQ) {
            nodeP = nodeP == null ? headB : nodeP.next;
            nodeQ = nodeQ == null ? headA : nodeQ.next;
        }

        return nodeP;

    }

如有错误，欢迎指出。