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

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解答

解法一：暴力枚举，时间复杂度O(M*N)

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    for (ListNode p1 = pHead1; p1 != null; p1 = p1.next) {
        for (ListNode p2 = pHead2; p2 != null; p2 = p2.next) {
            if (p1 == p2) {
                return p1;
            }
        }
    }
    return null;
}

解法二：由于两个有公共节点的单链表形如‘Y’型，即链表尾端的节点都是公共的，所以从后往前找最后一个公共节点就是第一个公共节点。为了便于反向查找，使用两个辅助栈存储节点。空间复杂度O(M+N),时间复杂度也是O(M+N)