链接列表问题

Question

嗨......

如果我们给出两个链表（可能长度不同），使得从最后几个节点是常见的...我们如何找到第一个公共节点尽可能少的时间......？

该列表单独链接。有些节点从最后是很常见的，我们需要找到它们之间第一个共同的节点。

Answer 1

假设每个链表都有一个完全唯一的集合，我所看到的唯一方法是使用嵌套for循环，这将非常低效。如果数据集是不是唯一的，你可以使用第三方（链接）列表，只有独特的节点的缓存，但你仍然在寻找在澳的最坏情况（N²）

Answer 2

• 计数两份名单 - 为O（n ）
• 同时跳过列表长度之间的差的较长列表上
• 遍历列表，直到发现一个共同的节点 - 为O（n）

总复杂性：O（n）的

例如：

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

我们期望得到，因为它是第一个通用节点。

1. 计数的清单 - 第一= 6，第二= 4
2. 跳过两个（6-4 = 2）在第一（较长的）列表元素。
3. 同时迭代
   3.1。 3 == 5是假的
   3.2。 4 == 6是假的
   3.3。 7 == 7是真的，那么7是公共节点

Answer 3

O（n）解决方案找到具有相同值的列表中的第一个节点。然后您可以从该节点提取值。

除非另有说明，并且没有嵌套的O(n)操作，否则所有代码段（注释）均为O(1)。因此整个解决方案是O（n）。

它通过计算每个列表中的元素，然后推进最长列表的指针，使两端对齐。

然后它以同步的方式遍历两个列表。如果节点匹配并且先前未匹配，则节点保存该节点（而不是，如果它们匹配，因为您想在序列中匹配最早的）。

如果它们不匹配，则保存该事实，以便后续匹配将被视为序列中最早的匹配。

当您到达两个列表的末尾时，您或者显示没有匹配（如果两个列表的最后一个节点不同）或者序列中最早的匹配。

伪代码只当然，因为它的功课：

def findCommonNode (head1, head2): 

    # Work out sizes O(n) 

    set count1 and count2 to 0 

    set ptr1 to head1 
    while ptr1 is not equal to NULL: 
     increment count1 
     set ptr1 to ptr1->next 

    set ptr2 to head2 
    while ptr2 is not equal to NULL: 
     increment count2 
     set ptr2 to ptr2->next 

    # If either size is 0, no match possible. 

    if count1 == 0 or count2 = 0: 
     return NULL 

    # Make the first list longer (or same size). 

    if count1 < count2: 
     swap count1 and count2 
     swap head1 and head2 (local copies only) 

    # Move through longest list until they're aligned O(n). 

    set ptr1 to head1 
    set ptr2 to head2 

    while count1 is greater than count2: 
     decrement count1 
     set ptr1 to ptr1->next 

    # Initially mark as non-match. 

    set retptr to NULL 

    # Process both (aligned) lists O(n). 

    while ptr1 is not equal to NULL: 
     # If equal and if first match after non-match, save position. 

     if ptr1->data is equal to ptr2.data: 
      if retptr is equal to NULL: 
       set retptr to ptr1 
     else: 
      # If not equal, mark as non-match. 

      set retptr to NULL 

     # Advance to next element in both lists. 

     set ptr1 to ptr1->next 
     set ptr2 to ptr2->next 

    # Return the earliest match. 

    return retptr 

比方说，你有两个列表1,2,3,4,5,5,6,7,8,9和0,6,9,8,9。对齐这些并根据大小差异推进列表1指针，您将获得：

  v 
1 2 3 4 5 5 6 7 8 9 
      0 6 9 8 9 
     ^

然后将匹配设置为NULL并开始处理。它们不匹配（5/0），因此您将第一个匹配节点设置为NULL（即使它已经为NULL）并且前进到6/6。

这些（6/6）匹配（并且当前匹配为NULL），因此您将其中一个地址保存为匹配，然后前进。

7/9不匹配，所以您再次将匹配设置为NULL，然后前进。

8/8匹配和匹配是NULL，所以你再次将匹配设置为其中之一，然后前进。

9/9也匹配但匹配已经设置，所以你不会改变它。提前，然后退出这两个列表中的元素。

然后您返回与8节点之一匹配。这是您最常见的尾部部分。