c - 链表问题

Question

嗨...

如果给定两个链表(可能长度不同)，从末尾开始有几个节点是公共(public)的……我们如何尽可能在最短的时间内找到第一个公共(public)节点……？

列表是单向链接的。有些节点从头到尾都是公共(public)的，我们需要从头到尾找到它们之间的第一个公共(public)节点。

Answer 1

• 计算两个列表 - O(n)
• 跳过较长列表中列表长度之间的差异
• 同时遍历列表直到找到公共(public)节点 - O(n)

总复杂度:O(n)

例如:

1->2->3->4->7->8
----------5->6->7->8

我们希望得到 7，因为它是第一个公共(public)节点。

1. 计算列表 - 第一个 = 6，第二个 = 4。
2. 跳过第一个(较长)列表中的两个 (6-4=2) 个元素。
3. 同时迭代
   3.1. 3==5 为假
   3.2. 4==6 是假的
   3.3. 7==7为真则7为公共(public)节点