题意：

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

原题链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

方法一：辅助栈

使用两个栈 和 ，分别存储链表 和 ，一开始将 和 都存入栈中。使用 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;
    }
}

复杂度分析

方法二：快慢指针

先计算两条链表的长度，然后计算长度差 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;
}

复杂度分析：

方法三：

假设链表 的非公共长度为 ，链表 的非公共长度为 ，二者的公共长度为 。

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

如果两个链表没有公共部分，即 ，那么走完两条链表后，会指向 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;
}

复杂度分析