数据结构链表

-1

我被要求解决这个问题：数据结构链表

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

实施例：

给出：

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

返回值将是一个指向构件 - 8.

但是，我需要做的是在不改变列表或使用更多的内存，和 - 我们需要扫描列表只有一次，意味着T(n)=O(n)。

来源

2017-07-05 Roi Zrihan

这肯定看起来像一个家庭作业的问题。堆栈溢出不会为你做功课。写一些代码，试着让它工作，然后当你遇到特定问题时寻求帮助。 – AlienHoboken

你在编写什么编程语言？ – Yonlif

列表是否保证排序？ – wildplasser

措施两份名单的长度
快进在较长的列表中，直到它们是相同的长度
向前步行通过步骤两个列表，并记住节点的最后一个点之后，其中的列表有不同的元素。这些是你可以返回的指针。

现在......我知道你说你只需要扫描列表一次，我做了两次，但你也表示，这意味着T（N）= O（N），那就是不是是正确的。

扫描列表两次是也在为O（n）和需要解决的问题，而无需使用额外的无界存储器。

来源

2017-07-06 03:52:37

这将需要*至少两次通过列表。 – wildplasser

@wildpasser如上所述，它只需要两遍 - 每个列表需要一遍才能进行测量，并且在（2）和（3）中的每个项目上只有一步。 –

这是一个伪代码..不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

来源

2017-07-06 07:26:44

数据结构链表

回答

相关问题