两个链表的第一个公共结点

题目

输入两个链表，找出它们的第一个公共结点。

思路

这道题和160.Intersection of Two Linked Lists是一样的。都是求两个链表的第一个公共结点。

公共结点的样子：

 

上图就是一个有公共结点的例子，在公共结点之后，两个链表指针指向的地址是相同的。

这道题有两个解法。

方法一：

我们可以把两个链表拼接起来，一个pHead1在前pHead2在后，一个pHead2在前pHead1在后。这样，生成了两个相同长度的链表，那么我们只要同时遍历这两个表，就一定能找到公共结点。时间复杂度O(m+n)，空间复杂度O(m+n)。

方法二：

我们也可以先让把长的链表的头砍掉，让两个链表长度相同，这样，同时遍历也能找到公共结点。此时，时间复杂度O(m+n)，空间复杂度为O(MAX(m,n))。

代码

栈

public static ListNode FindFirstCommonNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    if (headA == headB) {
        return headA;
    }
    Stack<ListNode> st1 = new Stack<>();
    Stack<ListNode> st2 = new Stack<>();
    while (headA != null) {
        st1.push(headA);
        headA = headA.next;
    }
    while (headB != null) {
        st2.push(headB);
        headB = headB.next;
    }
    if (st1.peek() != st2.peek()) {
        //如果链表最末尾的节点都不相同，那么说明没有公共节点；（该行该函数最后一行搭配）
        return null;
    }
    while (st1.size() != 0 && st2.size() != 0 && st1.peek() == st2.peek()) {
        st1.pop();
        st2.pop();
    }
    if (st1.size() == 0){
        //如果st1先遍历结束，说明st1的第一个节点就是公共节点，也即st2栈顶元素的next指针指向的节点；
        return st2.peek().next;
    }
    else if(st2.size() == 0) {
        //同理，如果st2线遍历结束，说明st2的第一个节点就是公共节点；
        return st1.peek().next;
    }
    else {
        return st1.peek().next;
        //这一行和第34行搭配，如果st1和st2都不为空，但是两栈栈顶元素的值不相等，那么最近栈顶元素的next指针指向的元素就是公共节点；
    }
}

双指针法

创建两个指针 pApA 和 pBpB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。

当 pApA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pBpB 到达链表的尾部时，将它重定位到链表 A 的头结点。

若在某一时刻 pApA 和 pBpB 相遇，则 pApA/pBpB 为相交结点。

想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。 由于 B.length (=4) < A.length (=6)，pBpB 比 pApA 少经过 2 个结点，会先到达尾部。将 pBpB 重定向到 A 的头结点，pApA 重定向到 B 的头结点后，pBpB 要比 pApA 多走 2 个结点。因此，它们会同时到达交点。

如果两个链表存在相交，它们末尾的结点必然相同。因此当 pApA/pBpB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}