两个链接列表的交集

给定两个排序链接列表L1和L2，计算它们的交点的解决方案L1交叉点L2。两个链接列表的交集

2010-01-31 AJ.

SO的目的是灌输知识和理解，而不是给你模糊问题的完整解决方案。 – 2010-02-02 22:24:22

L1_node = L1.head; 
L2_node = L2.head; 
Result = new SList; 
while L1_node != NULL and L2_node != NULL: 
    if L1_node.value == L2_node.value: 
    Result.append(L1_node.value) 
    L1_node = L1_node.next 
    L2_node = L2_node.next 
    elif L1_node.value < L2_node.value: 
    L1_node = L1_node.next 
    else 
    L2_node = L2_node.next

（翻译到C自己）

来源

2010-01-31 11:19:01 kennytm

这是一个错误。在==情况下，你不会跳过任何东西 - 你会得到无限的L1_node.value系列。 – Steve314 2010-01-31 11:26:51

也许它是作为OP的调试练习而留下的？如果我要雇用一个人，并提出了这个确切的面试问题，并得到了这个确切的解决方案，我会质疑他作为程序员开始工作的动机，如果他只是简单地将他在网上找到的答案撇在一边。 – 2010-01-31 11:40:26

@Lasse - 也许，并不是一个坏主意。我的下面的错误是故意的，诚实的<隐藏在公然谎言中的羞耻>。 – Steve314 2010-01-31 11:51:19

-1

的基本方法，以按顺序合并样的算法是，你永远需要考虑在同一时间超过三个项目 - 从每个输入前项列表，以及潜在的保存结果。

在这种情况下，我会用...

loop forever 
    while in1.value < in2.value : transfer item from in1 to output 
    while in2.value < in1.value : transfer item from in2 to output 

    if in1.value == in2.value : 
    transfer item from in1 to output 
    discard item from in2 

    while in1.value == value just transferred : disard item from in1 
    while in2.value == value just transferred : disard item from in2

现在讨厌的 - 这个循环假设表是无限的。你如何处理空列表？这很烦琐，除非你能保留一个sentinel value，该值大于列表中可能出现的任何合法值。

如果你不能保留一个哨兵，你可以伪造这个效果 - 编写一个比较函数，在比较值之前检查每个队列中是否有下一个项目，并将“队列穷尽”看作是哨兵值。

这给了...

loop forever 
    while in1.value < in2.value : discard item from in1 
    while in2.value < in1.value : discard item from in2 

    if in1 exhausted, break out of loop 
    if in2 exhausted, break out of loop 

    if in1.value == in2.value : 
    transfer item from in1 to output 
    discard item from in2 

    while in1.value == value just transferred : discard item from in1 
    while in2.value == value just transferred : discard item from in2

OOPS

这是一个工会。转换为十字路口是作为读者的练习。

编辑

确定 - 它现在是一个交集。只是抛弃不足的项目，而不是将它们添加到输出中。还修复了一个错字。

注意 - 我的解释是交集的输出应该是一个集合，意思是没有重复。这容忍在输入中的重复，但输出是免费的。

来源

2010-01-31 11:39:50 Steve314

下面的解决方案如何，它是O（n + m），并采取指向头节点的虚拟节点。 Head节点在这里是一个类级别的变量，所以即使L1指向当前，Head总是拥有完整的列表。

我已编译和测试，运行良好像L1简单输入：1-> 5> 6> 7> 8> 10和L2：2> 4> 6> 8时，输出为6> 8

任何有关如何去未排序列表的想法？我不能认为一个为O（n）溶液

public Node ReturnIntersection(Node Head, Node L2) { if ((Head == null) || (L2 == null)) return null;

 Node temp = null; 
     Node L1 = Head; 


     while (L1.next != null && L2.next != null) 
     { 
      if (L1.data == L2.data) 
      { 
       L1 = L1.next; 
       L2 = L2.next; 
      } 

      else if (L1.data < L2.data) 
      { 
       temp = L1.next; 
       L1.data = temp.data; 
       L1.next = temp.next; 

      } 

      else if (L1.data > L2.data) 
      { 
       L2 = L2.next; 

      } 

     } 

     if (L1 != null) 
     { 
      while (L1.next != null) 
      { 
       L1.next = null; 

      } 
     } 
     return Head; 


    }

来源

2011-03-24 21:03:58 RashMans

的由于它们是单链表如果两个链表相交他们会形成Y形状与一个臂长于或等于另一个。令l1为L1列表的长度，l2为L2列表的长度。

假设l1> l2。从点（l1-l2）开始匹配列表L1的指针，并从它的开始匹配列表L2，并指向同一节点，该节点将作为匹配点。

如果l2大于l1，则采用其他方式。

来源

2011-08-07 10:08:07 john

两个链接列表的交集

回答

相关问题