剑指 Offer 52. 两个链表的第一个公共节点

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

方法一：辅助栈

使用两个栈 $S1$ 和 $S2$ ，分别存储链表 $A$ 和 $B$，一开始将 $A$ 和 $B$ 都存入栈中。使用 ans 指向最终答案。

然后不断弹出，弹出的过程中，判断两个节点是否相等，如果相等则记录下来，$ans$ 指向相等的节点，然后继续弹出直到两个节点不相等，则 $ans$ 指向的节点就是最终答案。

代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Deque<ListNode> sA = new LinkedList<>();
    Deque<ListNode> sB = new LinkedList<>();
    putIntoStack(headA, sA);
    putIntoStack(headB, sB);
    ListNode ans = null;
    // 判断是否有共同节点
    boolean intersect = false;
    while (!sA.isEmpty() && !sB.isEmpty()) {
        ListNode a = sA.pop();
        ListNode b = sB.pop();
        if (a != b) {
            return ans;
        }
        intersect = true;
        ans = a;
    }
    return intersect ? ans : null;
}

private void putIntoStack(ListNode head, Deque<ListNode> stack) {
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
}

复杂度分析

• 时间复杂度$O(MN)$：$M$、$N$ 分别为两个链表的长度。
• 空间复杂度$O(MN)$：辅助栈最多要存储两个链表的所有节点。

方法二：快慢指针

先计算两条链表的长度，然后计算长度差 d，快指针现在先对较长的链表上走 d 步。然后慢指针在快指针走了 d 步后，两条指针同时走。

• 如果快慢指针指向的节点相同，那么它是第一个公共节点；
• 如果快慢指针直到走完都没有相等，那么不存在公共节点。

代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 比较两条链表的长度，得出二者的长度差值 d
    // 长的那条链表的指针先走 d 步，然后两个链表指针同时走，第一次相等时，就是第一相交节点
    int lenA = listLen(headA);
    int lenB = listLen(headB);
    ListNode smaller, bigger;
    smaller = lenA < lenB ? headA : headB;
    bigger = smaller == headA ? headB : headA;
    int diff = Math.abs(lenA - lenB);
    while (diff > 0) {
        bigger = bigger.next;
        diff--;
    }
    while (smaller != null && bigger != null) {
        if (smaller == bigger) {
            return smaller;
        }
        smaller = smaller.next;
        bigger = bigger.next;
    }
    return null;
}

private int listLen(ListNode head) {
    int ans = 0;
    while (head != null) {
        ans++;
        head = head.next;
    }
    return ans;
}

复杂度分析：

• 时间复杂度$O(MN)$：$M$、$N$ 分别为两个链表的长度。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。

方法三：

假设链表 $A$ 的非公共长度为 $a$，链表 $B$ 的非公共长度为 $b$，二者的公共长度为 $c$。

观察上图，如果先走完链表 $A$ 然后再走链表 $B$ 的 $b$ 部分，可以到达公共点。同样的，如果先走完链表 $B$ 然后再走链表 $A$ 的 $a$ 部分，可以达到公共点。关系如下：

如果两个链表没有公共部分，即 $c = 0$，那么走完两条链表后，会指向 null 。

关系如下：

代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = a != null ? a.next : headB;
        b = b != null ? b.next : headA;
    }
    return a;
}

复杂度分析

• 时间复杂度$O(MN)$：$M$、$N$ 分别为两条链表的长度。
• 空间复杂度$O(1)$：辅助变量占用常数大小的空间。