c - 如何在 C 中合并和排序两个双向链表

Question

我目前正在开展一个项目，该项目接受两个包含数据的文本文件并将它们分类到两个单独的链表中。我的下一步是创建一个函数，该函数接受这两个列表以合并并按 ID 升序对它们进行排序。我已经开始实现，但我被卡住了，需要一些指导来了解我在合并排序功能上做错了什么。其他一切都正常工作，例如单独对每个列表进行排序。我只需要一种方法来接收这两个列表并在 C 中将它们合并排序。注意:我使用的是 Ubuntu gcc 编译器。

struct List *merge_list(struct List *list1, struct List *list2)
{
    struct Node *hand1 = list1->head;
    struct Node *hand2 = list2->head;
    struct Node *tmp1, *tmp2 = NULL;
    struct List *list3 = malloc(sizeof(struct List));

    while(list1 && list2 != NULL)
    {
            if(ptr1->id > ptr2->id)
            {
                    ptr1 = list3->head;
                    ptr1 = ptr1->next;
            }
            else
            {
                    ptr2 = list3->head;
                    ptr2 = ptr2->next;
            }
    }
    return list3;
}

注意:这是我的节点和列表结构

struct Node {
  int id;
  char *fname;
  char *lname;
  char *department;
  float gpa;
  struct Node *next;
  struct Node *prev;
};

struct List {
  struct Node *head;
  struct Node *tail;
  int count;
};

Answer 1

合并两个排序列表:

while (hand1 && hand2) {
    if (hand1->id <= hand2->id) {
        tmp = hand1;
        hand1 = hand1->next;
    } else {
        tmp = hand2;
        hand2 = hand2->next;
    }

    insertNode(list3, tmp);
}

// either hand1 or hand2 will have some leftover elements
// they can be added to the back of list by inserting the head
if (hand1)
    insertNode(list3, hand1);
else
    insertNode(list3, hand2);

我留给你编写 insertNode()。为了保持两个列表的排序，它应该在列表的末尾插入节点。这应该很容易，因为您正在跟踪列表的尾部。

我会将 list3 中的指针初始化为 NULL，并将计数初始化为 0，这应该使编写 insertNode() 更容易。