在不使用内置排序方法的情况下在 C++ 中合并两个链表

Question

给你两个链表，其中一个已排序，另一个不是任务，你必须合并它们并对它们的值进行排序，同时在执行过程中进行比较，而不是分别对两个链表进行排序，并且也不使用 C++ 模板库中的任何内置方法。

我自己尝试过这个问题，但没有成功。我觉得是在if条件下接近无限循环条件了！

这是我所做的：

#include <iostream>

using namespace std;
struct Student {
    int id;
    Student *next = NULL;
};
Student *first = NULL;
Student *last = NULL;
Student *first2 = NULL;
Student *last2 = NULL;

void display(Student *k);

void insert_end(Student *k);

void merge();

int main() {
    int exit = 1;
    do {
        cout << "11.Display, 12.Insert, 3.Merge\n";
        cout << "21.Display, 22.Insert, 0:exit\n";
        cin >> exit;
        switch (exit) {
            case 11:
                display(first);
                break;
            case 12:
                insert_end(last);
                break;
            case 3:
                // first = mergeTwoLists(first, first2);
                //merge();
                Student* SortedMerge(Student* a, Student* b);
                break;
            case 21:
                display(first2);
                break;
            case 22:
                insert_end(last2);
                break;
            default:
                cout << "WRONG\n";
                break;
        }
    } while (exit != 0);
    return 0;
}

void display(Student *k) {
    Student *p = k;
    while (p != NULL) {
        cout << "ID: " << p->id << "\n";
        p = p->next;
    }
}

void insert_end(Student *k) {
    cout << "This is the function of insert_end \n";
    Student *current = new Student;
    cout << "Enter ID: ";
    cin >> current->id;
    if (k == NULL) {
        if (k == last) {
            first = last = current;
        } else {
            first2 = last2 = current;
        }
    } else {
        if (k == last) {
            last->next = current;
            last = current;
        } else {
            last2->next = current;
            last2 = current;
        }
    }
}
void merge() {
    Student *p1 = first;
    Student *p2 = first2;
    while (p1 != NULL) {
        p2 = first2;
      while (p2->next != NULL) {
            if (p1->id <= p2->id) {
                Student *curr = p2;
                curr->next = p1->next;
                p1->next = curr;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

可能的优化解决方案是什么？

Answer 1

你需要先重写函数insert_end。最初两个指针 last 和 last2 都是空指针

Student *first = NULL;
Student *last = NULL;
Student *first2 = NULL;
Student *last2 = NULL;

因此，如果用户首先决定填写第二个列表，那么由于这个 if 语句

if (k == NULL) {
    if (k == last) {
        first = last = current;
    } else {
        first2 = last2 = current;
    }
}

该函数将在第一个列表而不是第二个列表中插入一个新节点。

函数merge也是错误的。对于初学者来说，它既不改变 first 也不改变 first2 也不改变 last 和 last2.

如果if语句

if (p1->id <= p2->id) {
    Student *curr = p2;
    curr->next = p1->next;
    p1->next = curr;
}

授予控制权，然后指针 p2 的数据成员 next 由于这些行

而改变

    Student *curr = p2;
    curr->next = p1->next;

即第二个链表指针的数据成员next指向第一个链表的结点

但是在 if 语句之后

p2 = p2->next;

指针p2指向第一个列表中的节点，而不是指向第二个列表中的节点。

为了让生活更轻松，您需要再定义一个结构，例如

struct List
{
    struct Student *first;
    struct Student *last;
};

并为这种结构类型的指针定义函数。

在不使用内置排序方法的情况下在 C++ 中合并两个链表

Merge two Linked List In c++ without using inbuilt sort method

c++

sorting

merge

struct

linked-list