数据结构链表

Question

我被要求解决这个问题：

有两个单链表。 我需要编写一个方法来获取这两个链表，并返回一个指向这两个列表中后缀相同的起点的指针。

例：

鉴于：

1->2->4->6->8->10->15
2->4->8->10->15

返回的值将是指向成员 - 8 的指针。

但 我需要在不更改列表或使用更多内存的情况下执行此操作， 和 - 我们只需要扫描一次列表，意味着T(n)=O(n).

Answer 1

1. 测量两个列表的长度
2. 在较长的列表中向前跳跃，直到它们的长度相同
3. 逐步浏览两个列表，并记住列表具有不同元素的最后一点之后的节点。 这些是您可以返回的指针。

现在。。。我知道你说你只想扫描一次列表，我已经扫描了两次，但你也说这意味着T(n) = O(n)，这是不正确的。

扫描列表两次也是O(n)格式，并且需要在不使用无限额外内存的情况下解决问题。

Answer 2

这是一个伪代码..不是Python代码 取两个列表，让 P1 指向较长的列表，P2 指向较短的列表，

while p1->next!=NULL:
if p1->value = p2->value:
p1 = p1->next
p2 = p2->next
else:
p1 = p1->next
returnpointer = p1->next// if it happens that some elements are same towards end but not the last element.. p1->next would be pointing to NULL anyways and else.. it'll always be the element next to the last element which wasn't same
return returnpointer