题目描述

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

题解

本题可以将两个链表的节点存放在两个栈中，这样两个链表的尾节点就位于栈顶，然后依次比较栈顶是否相同，得到最后一个相同的栈顶元素即为两个链表的第一个公共节点。但是这种方法需要两个辅助栈，时间复杂度和空间复杂度都是O(m+n)。

还有一个更简单的方法，可将空间复杂度降至O(1)。首先遍历两个链表，统计两个链表长度的差值。然后先在较长的链表上先走若干步，步数为这些差值。最后同时在两个链表上开始遍历，找到第一个公共节点。

public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
    if (head1 == null || head2 == null)
        return null;
    // 首先遍历两个链表，统计两个链表长度的差值。
    ListNode p = head1, q = head2;
    int count1 = 0, count2 = 0;
    while (p != null) {
        count1++;
        p = p.next;
    }
    while (q != null) {
        count2++;
        q = q.next;
    }
    // 先在较长的链表上先走若干步，步数为这些差值。
    if (count1 > count2) {
        int diff = count1 - count2;
        while (diff > 0) {
            head1 = head1.next;
            diff--;
        }
    } else {
        int diff = count2 - count1;
        while (diff > 0) {
            head2 = head2.next;
            diff--;
        }
    }
    // 最后同时在两个链表上开始遍历，找到第一个公共节点。
    while (head1 != head2) {
        head1 = head1.next;
        head2 = head2.next;
    }
    return head1;
}