查看两个链表是否相等的算法

Question

我有一个算法比较两个链表L1和L2和相同的元素，它将它们放在第三个列表L3中，同时将它们从L2中删除。我不确定，但如果这是算法应该做的全部内容，并且我不理解某些概念，例如“p1prec”。我想合理地知道算法的设计，更大的画面。当我试图通过逐一检查指示来获得它的感觉时，我觉得我正试图记住它。同样在方法设计相似的算法提出了一些建议会相当welcome.The算法如下：

Equal(L1,L2) 

    head[L3] = NIL   //L3 is empty 
    if head[L2] = NIL   //if there are no elements in L2 return NIL 
     return L3 
    p1 = head[L1]    //p1 points the head of L1 
    p1prec = nil    //p1prec is supposed to be precedent I guess. 
    while p1 =/= nil 
      p2 = head[L2]  //p2 points head of L2 
      p2prec = nil  //p2prec is precedent of p2; first cycle is nil 
      while p2 =/= nil and key[p1] =/= key[p2] 
       p2prec = p2   // pass p2 and p2prec through L2 until 
       p2 = next[p2]  // key[p1] = key[p2] 
      if p2 =/= nil  // if two elements are found equal 
       next[p1prec] = next[p1]   // im not sure what this does 
       insert(L3,p1)     // insert the element in L3 
       p1 = next[p1prec]    //neither this, 
       next[p2prec] = next[p2] //connects the p2prec with nextp2 because p2 
       free(p2)       //is going to be deleted 
      p1prec = p1  //moves through L1, if no element of p2 is found   
      p1 = next[p1]       //equal with first element of p1 

Answer 1

因为我猜你的目标是了解如何做到这一点的问题，我将只是尝试基本算法解释给你，而不是告诉你每一行做什么的。

您有2个列表：L1和L2。

你基本上想要检查L1中的每个元素和L2中的每个元素。 设L1电流和L2电流为您正在检查的值。

您还需要L2Prec，因为当您删除L2元素时，您需要将prec与下一个链接。

You start with L1current = L1 and L2current = L2; 
While (L1current is not NULL) 
{ 
    L2current = L2; // you set the L2Current to the begging of L2 list. 
    While (L2current is not NULL) // you run untill the end. 
    { 
     You check if L1current == L2current; 
     { 
      // If they are equal 
      You add the L2 element to L3; 
      You connect L2prec with L2next; 
      You delete L2current; 
     } 
     Else 
     { 
       L2current = L2next; 
     } 
    } 
     L1current = L1next; // after you are done with the first element of L1 you 
          // move to the next one. 
} 

Answer 2

几件事情：

1）看来它是从L1和L2但这是去除填充一个小细节

2）你对算法和数据结构了解多少？你知道链表是​​如何工作的吗？如何实现一个？那里有什么类型，它们之间有什么区别？

我在问这是因为对单链表的基本理解很明显是什么p1(2)prec是什么next[p1(2)prec]是什么以及如何从单链表中删除工作。

也许先读一下关于列表应该是要走的路？

3）基本上如您所说，该算法迭代两个列表，如果它找到一个公共元素，它从两个列表中删除它并将其放入结果列表中（元素可以位于列表中的sam位置但不必 - 如果这是你想要的，那是一个不同的问题:-)。

一个单独（这是这里重要的）链表看起来或多或少是这样的：

prec p1 next[p1] 
el1 -> el2 -> el3 -> nil 

你只能去从左至右。现在让我们删除“el2”。但等待我们在“el2”，那么我们如何改变指针，使“el1”指向“el3”呢？

那么这就是“prec”在这个算法中的用处。在SLL中，您将更改为前一个指针所指向的位置，就是这样！你删除了你的元素：

EL1 - > EL3 - >零

为什么会这样呢？还记得我说你只能从左到右走到这里吗？那么你把指针从next[el1]更改为el3，所以右边的下一个元素el3，即使我们不会对free执行访问，也无法访问el2。

这里free(p2)也从第二个列表中释放元素使用的内存。请注意，它只对p2有效，因为p1已插入到L3中，所以我们仍然需要它。

取决于语言/实现这一行：

next[p1prec] 

可能会出现问题。如果第一个元素是平等的呢？然后p1prec和p2prec仍然是零，但是你正试图对它们进行一些操作。但正如我所说，这是一个实施细节。（如果我没有遗漏任何东西），因为对于L1中的每个元素，你都会（在最坏的情况下）完全遍历L2（注意，在while p1 =/= nil p2点之后）再次在头元素）。

这基本上...