c++ - 合并链表时输出错误

Question

目前我有以下函数来合并两个mylist 类型的已排序链表。目前，有一些错误我至今无法查明和修复。该函数基本上应该做的是，假设 A = 1 2 3 和 B = 3 4 5。然后当我合并两者时(假设两个列表都已排序)，A 将变为 1 2 3 3 4 5 并且 B 将变为 空。

目前，例如，当我尝试 A = 1 2 3 和 B = 4 5 6 并将两者合并时，A变为 6 并且 B 变为 4。我知道算法有问题，但我还不能查明并修复。我是编程新手。任何帮助将不胜感激!

void mylist::merge(mylist& b)
{

    if (!this->isSorted() || !b.isSorted())
        cout << "error" << endl;

    Node* ptr1 = b.head;

    Node* prev_a = NULL;
    Node* curr_a = head;
    Node* curr_b = ptr1;

    while (curr_b) {
        if (curr_a && head < ptr1) {
            prev_a=curr_a;
            curr_a = curr_a->next;
        }
        else {
            Node* b_next = curr_b->next;
            curr_b->next = curr_a;

            if (prev_a) prev_a->next = curr_b;
            else head = curr_b; // curr_b is first element in 'a'

            if (curr_a) {
                prev_a = curr_a;
                curr_a = curr_a->next;
            }
            curr_b = b_next; 
        }
    }
    return;

}

编辑:

我已经按照提到的进行了以下更改，但是在合并 A = 1 2 3 之后我仍然得到 A = 6 和 B = 4 & B = 4 5 6。

void mylist::merge(mylist& b)
{

    if (!this->isSorted() || !b.isSorted())
        cout << "error" << endl;

    Node* ptr1 = b.head;

    Node* prev_a = NULL;
    Node* curr_a = head;
    Node* curr_b = ptr1;

    while (curr_b) {
        if (curr_a && head->key < ptr1->key) {
            prev_a=curr_a;
            curr_a = curr_a->next;
        }
        else {
            Node* b_next = curr_b->next;
            curr_b->next = curr_a;

            if (prev_a) prev_a->next = curr_b;
            else head = curr_b; // curr_b is first element in 'a'

                prev_a = curr_a;

            curr_b = b_next; 
        }
    return;

}

Answer 1

1)排序问题:

在你的指令中

    if (curr_a && head < ptr1) {    // argh !!!

你比较两个指向Node的指针(即他们的地址)而不是指向的值。

2) 极端情况(适用于您的测试数据):

如果列表的第一个元素 b大于列表 a 的任何元素(假设你已经纠正了问题 #1)，那么你将循环直到 curr_a为空，从未设置 prev_a .然后，您可以将 b 的元素插入到 a 的头部(以相反的顺序)

3)首先在列表a的中间合并:

在正常合并中，您可以循环遍历列表 a直到您拥有列表的第一个元素 b小于 a 的元素. prev_a目前还没有设置。因此，您将连接 b 的当前元素的下一个元素到 a 的当前元素(没关系)，但是，作为 prev_a为 NULL，您将连接 a 的头部到 b 的当前元素，因此丢失了 a 中的整个元素链那是在当前的之前。

解决步骤:

如果是老师布置的作业:

while (curr_b) {
    if (curr_a && curr_a->key < curr_b->key) { // assuming data is stored in the node and has a comparator defined
        prev_a = curr_a;   // keep track of it (WAS MISSING)
        curr_a = curr_a->next;
    }
    else { 
        Node* b_next = curr_b->next;
        curr_b->next = curr_a;

        if (prev_a) prev_a->next = curr_b;
        else head = curr_b; 

        prev_a = curr_b;  // THE ELEMENT you've inserted is now prev_a
                          // curr_a SHALL not change since the next element of b can also be smaller than it 
        curr_b = b_next; 
    }
 }

如果是真正的代码，你真的应该考虑标准 <list>容器及其现有 merge() 功能;-)

编辑: 我刚刚意识到还有另一个问题并更新了上面循环中的 else 部分。而且我意识到我太专注于关键比较，以至于我没有注意到使用了错误的指针，所以它并没有在所有测试用例中都成功!