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

Question

>我有一个算法，它比较两个链表，L1和L2，以及相等的元素，它将它们放在第三个列表L3中，同时从L2中删除它们。我不确定这是否是算法应该做的全部，而且我不明白一些概念，例如"p1prec"。我想理性地了解算法的设计，更大的图景。当我试图通过逐个检查说明来理解它时，我觉得我试图记住它。此外，关于设计类似算法的方法的一些建议也将非常受欢迎。算法如下：

    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。

您基本上想用 L2 中的每个元素检查 L1 中的每个元素。让 L1current 和 L2current 成为您正在检查的值。

您还需要一个 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 仍然为零，但您正在尝试对它们进行一些操作。但正如我所说，这是一个实现细节。

4）这具有O（n^2）复杂性（如果我没有错过任何东西），因为对于L1中的每个元素，您（在最坏的情况下）都会完全遍历L2（请注意，while p1 =/= nil后p2再次指向头部元素）。

基本上就是这样...