我正在尝试以升序将两个链表合并为1个链表

Question

我刚接触链表，需要帮助理解如何将两个链表合并在一起。在我的程序中，除了以升序将两个列表合并在一起的功能之外，一切都可以正常工作。head和first是指向两个独立链表开头的指针。

  void linkedListType::AscendMerge()
  {
    nodeType * c1;
    nodeType * c2;
    nodeType * p1;
    nodeType * p2;
    c1 = first;
    c2 = head;
    p1 = first;
    p2 = head;

    while (c1->link&&c2->link != NULL)
    {
      if (c1->info <= c2->info)
      {
        c1->link->link = c2->link;

      }
      if (c2->info < c1->info)
      {
        c1->link = c2->link;

      }
      cout << c1->info << " ";
      c1 = c1->link;
      c2 = c2->link;
     }
   }

Answer 1

你的实现有两个问题。一个与算法本身有关，第二个与它在C++中的编码方式有关。

该算法的问题在于，您的代码不能处理列表的“尾部”：一旦其中一个列表的项用完，您的while循环就会调用它退出，留下第二个列表的剩余项“孤立”。

修复这一部分很简单:您只需将剩余的非空列表链接到结果的末尾。

编码问题有几个部分:首先，您的实现没有接收到要作为参数合并的两个列表：c1和p1都被分配了head，大概是将一个列表与自身合并。其次，while循环在到达列表末尾之前停止：c1->link为NULL意味着c1是最后一个节点；您的代码从不检查它的值。最后，您的代码不会返回合并后的列表。您的代码确实修改了link的值，但是当merge接触到head时，指针既不会被修改也不会返回。