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

题目：输入两个链表，找出它们的第一个公共节点。链表节点定义如下：

private static class ListNode {
    ListNode next;
    int value;
    public ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

首先我们会考虑蛮力法，我们在遍历第一个链表时，每访问一个节点，我们都会去第二个链表查看是否有相同的节点，如果有说明它们重合，这个节点即是它们的公共节点。如果第一个链表的长度为 $m$，第二个链表的长度为 $n$，那么时间复杂度为 $O(mn)$。

如果我们能从链表的尾部开始遍历的话，那么最后一个相同的节点即是它们第一个公共节点。但是由于题目所给出的链表是单向链表，不能从尾部开始遍历。但是我们可以考虑使用栈，我们在遍历两个链表时将节点添加到栈中，接着从栈中取出元素，是不是就相当于从尾部开始遍历链表了。使用这种方法需要 $O(m+n)$ 的时间复杂度和 $O(m + n)$ 的空间复杂度。

现在在考虑一种解法，我们首先获得两个链表的长度，假设第一个链表比第二个链表长 $k$，那么我们先让第一个链表先走 $k$ 步，接着同时遍历两个链表，这时它们会同时到达第一个公共节点，所以当它们遍历的节点相同时，我们就可以知道这个节点是第一个公共节点。该种方法的时间复杂度是 $O(m + n)$，但是不需要额外的空间复杂度。

public static ListNode findFirstCommonNode(ListNode root1, ListNode root2) {
    if (root1 == null || root2 == null) {
        return null;
    }
    int length1 = getListLength(root1);
    int length2 = getListLength(root2);
    ListNode ahead = root1;
    ListNode after = root2;
    // 如果链表 2 比链表 1 长，链表 2 先走
    if (length2 - length1 > 0) {
        ahead = root2;
        after = root1;
    }
    // 长的先走 k 步
    for (int i = 0; i < Math.abs(length2 - length1); i++) {
        ahead = ahead.next;
    }
    // 当访问的节点相同时，即是第一个公共节点
    while (ahead != null && after != null) {
        if (ahead == after) {
            return ahead;
        }
        ahead = ahead.next;
        after = after.next;
    }
    return null;
}
// 获得链表的长度
private static int getListLength(ListNode root) {
    ListNode cur = root;
    int length = 0;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}