面试题:两个链表的第一个公共结点题目:输入两个链
19 查阅
参考答案:
面试的时候碰到这道题,很多应聘者的第一反应就是蛮力法:在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样,说明两个链表在这个结点上重合,于是就找到了它们的公共结点。如果第一个链表的长度为m,第二个链表的长度为n,显然该方法的时间复杂度是O(mn)。
通常蛮力法不会是最好的办法,我们接下来试着分析有公共结点的两个链表有哪些特点。从链表结点的定义可以看出,这两个链表是单向链表。如果两个单向链表