c++ - C++ 合并链表问题

Question

所以我是 C++ 的初学者，我有一个学校项目来创建一个链表，我现在正在研究合并方法，我不确定为什么它不起作用。我发现问题出在第二个 if 在 while 循环中，而不是更改 head_ list 节点，而是更改 list1 列表，我不知道它为什么这样做

template <typename T>
bool List342<T>::Merge(const List342<T>& list1) {
    if (head_ == nullptr) {
        head_ = list1.head_;
        return true;
    }
    if (list1.head_ == nullptr) {
        return false;
    }
    Node<T>* l1_ptr = list1.head_;
    Node<T>* head_ptr = head_;
    while (l1_ptr != nullptr && head_ptr != nullptr) {
        if (*head_ptr->data == *l1_ptr->data) {
            l1_ptr = l1_ptr->next;
            head_ptr = head_ptr->next;
        }
        else if (*head_ptr->data <= *l1_ptr->data) {
            Node<T>* temp = head_ptr->next;
            head_ptr->next = l1_ptr;
            l1_ptr->next = temp;
            l1_ptr = l1_ptr->next;
            head_ptr = head_ptr->next;
        }
    }
    return true;
}

Answer 1

我发现通过列表迭代器的引用和递归更容易使用链接列表。此版本确保第二个链表处于有效状态（尽管可能已更改），并且不会分配新内存。

template <class T>
bool List342<T>::Merge(List342<T>& list1) {
  merge(head_, list1.head_);
}

template <class T>
void merge(List342<T>::Node*& head, List342<T>::Node*& head_o) {
  if (head_o == nullptr)
      return;

  if (head == nullptr) {
    head = head_o;
    head_o = nullptr;
    return;
  }

  if (*head->data <= *head_o->data) {
    merge(head->next, head_o);
  } else {
    // steal Node from right list1                                                                                             
    auto* next = head->next;
    auto* next_o = head_o->next;
    head->next = head_o;
    head_o->next = next;
    head_o = next_o; // this works because head_o is a reference                                                               
    merge(head->next, head_o);
  }
}

我认为这种代码使争论每种情况下发生的事情变得更加容易。如果您有任何问题，请告诉我。