如何将两个链接列表组合或合并以创建新列表？

Question

我正在尝试将两个链接列表“list_1”和“list_2”组合在一起，然后将它们组合成“list_3”。我创建了两个列表，似乎无法弄清楚如何组合它们。我添加的代码是我创建列表的方式。对指针和链表很新，所以任何帮助都将非常感谢，谢谢！

struct node
{
    int data;
    node *next;
};

class List
{
    public:
        node *head, *tail;
    List()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int n)
    {
        for(int i = 1; i <= 1; i++)
        {
            node *temp = new node;
            temp -> data = n;
            temp -> next = NULL;

            if(head == NULL)
            {
                head = temp;
                tail = temp;
            }
            else{
                tail -> next = temp;
                tail = tail -> next;
            }
        }
    }

Answer 1

你必须“重新连接”他们。列表B的head应重新连接到列表A的tail，以便您可以删除列表B的List对象，但不会删除其成员。介绍新方法merge(List* list)参数，并将this->tail重新连接到list->head，并更新this->tail成为list->tail。

Answer 2

如何将两个链接列表组合或合并以创建新列表

只需使用add_node迭代两个列表进行组合

这里有一个提案，其中combine修改当前列表，如果你喜欢这些方法，很容易添加一个新的构造函数获取参数中的两个列表或静态方法组合等

我添加了一些“经典”方法来帮助并能够在没有内存泄漏的情况下使用valgrind，并且还将List属性设置为私有，因为将它们公开不是一个好方法

#include <iostream>

struct node
{
  int data;
  node * next;

  node(int v) : data(v), next(nullptr) {}
};

class List
{
  private:
    node *head, *tail;

  public:
    List() : head(nullptr), tail(nullptr) {}
    ~List() { clear(); }
    List & operator=(const List & l) {            
      clear();

      const node * n = l.head;

      while (n != nullptr) {
        add_node(n->data);
        n = n->next;
      }
      return *this;
    }
    // + copy constructor, move etc

    void clear() {
       while (head != nullptr) {
         tail = head->next;
         delete head;
         head = tail;
       }
       head = tail = nullptr;
    }

    void add_node(int n)
    {
      node * temp = new node(n);

      if(head == NULL)
      {
        head = temp;
        tail = temp;
      }
      else
      {
        tail -> next = temp;
        tail = tail -> next;
      }
    }

    void combine(const List & l1, const List & l2) {
      *this = l1;

      node * n = l2.head;

      while (n != nullptr) {
        add_node(n->data);
        n = n->next;
      }
    }

    void pr() const {
      const node * n = head;

      while (n != nullptr) {
        std::cout << n->data << ' ';
        n = n->next;
      }
      std::cout << std::endl;
    }
};

int main()
{
  List l1, l2, l3;

  l1.add_node(1);
  l1.add_node(2);
  l1.add_node(3);

  l2.add_node(4);
  l2.add_node(5);

  l3.add_node(33);
  l3.pr();
  l3.combine(l1, l2);
  l3.pr();
}

编译和执行：

/tmp % g++ -pedantic -Wextra -Wall c.cc
/tmp % ./a.out
33 
1 2 3 4 5 

在valgrind下执行

/tmp % valgrind ./a.out
==8413== Memcheck, a memory error detector
==8413== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==8413== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==8413== Command: ./a.out
==8413== 
33 
1 2 3 4 5 
==8413== 
==8413== HEAP SUMMARY:
==8413==     in use at exit: 0 bytes in 0 blocks
==8413==   total heap usage: 11 allocs, 11 frees, 176 bytes allocated
==8413== 
==8413== All heap blocks were freed -- no leaks are possible
==8413== 
==8413== For counts of detected and suppressed errors, rerun with: -v
==8413== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)