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

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.
}