c - 将已排序的链表与头节点合并

Question

我正在编写一个void函数void merged_lists(cell * l1, cell * l2, cell * l3); who接收两个以l1和l2为首的链表，其内容按非降序排列，生成一个以l3为首的新链表，其中包含有序的l1和l2的元素。

如果以l1为首的列表为l1 -> 1 -> 7 -> 9 -> 10 -> NULL，以l2为首的列表为l2 -> 2 -> 3 -> 8 -> NULL，例如，输出必须是 l3 -> 1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> NULL

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

void display (node *le){

    node *p = le->next;

    while(p != NULL ){
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");

}

void MergeLists(node *l1, node *l2, node *l3) {
  if (!l1) 
    l3 = l2;
  if (!l2) 
  l3 = l1;

    //Chosing head of merged list
  if (l1->data < l2->data) {
    l3->next= l1;
  } else {
    l3 = l2;
    l2 = l1;
    l1 = l3;
  }

  while(l1->next && l2->next) {
    if (l1->next->data > l2->data) {
    //Step 1. Save the next pointer
      node *tmp = l1->data;
    //Step 2. Change next pointer to point L2
      l1->next = l2;
    //Step 3. Move L2 to temp
      l2 = tmp;
    }
    //Step 4. Move L1 ahead
    l1 = l1->next;
  } 
  if (!l1->next) l1->next = l2;
  display(l3);
}

我的 l1->1->7->9->10->11 和 l2->2->3->3->8 的输出是 0 -> 1 -> 2 -> 3 -> 3 -> 7 -> 9 -> 10 -> 11 -> NULL。

关于如何在一开始就解决这个问题有什么建议吗？

(我知道我之前发布了类似的问题，但随着焦点的变化，我认为再发一篇帖子是公平的)

Answer 1

这段代码存在第一个问题

if (!l1) 
    l3 = l2;
if (!l2) 
    l3 = l1;

您可以使用 l2 或 l1 的值覆盖 l3。结果是内存泄漏，因为 l3 所引用的头节点没有更多引用。

如果调用者对 l3 的头节点有引用，则在调用后他仍会看到一个空列表，因为 l3 的头节点尚未修改。

您应该将l1或l2的所有节点复制到l3中，以便l1和 l2 保持不变，l3 是其中之一的副本。

这段代码也有问题

//Chosing head of merged list
if (l1->data < l2->data) {
    l3->next= l1;
} else {
    l3 = l2;
    l2 = l1;
    l1 = l3;
}

您将l1 的头节点分配给l3->next。这意味着l3的头节点之后的第一个节点是l1的头节点。由于头节点不包含相关值，因此会产生错误的结果。

另一个问题出现在 else block 中。同样，您覆盖了 l3 的值，从而释放了对 l3 头节点的引用。 MergeLists 函数的调用者不会看到 l3 中的更改。调用后它仍然是一个空列表。

另一个问题是下面的行无法编译。你真的编译并运行了你的程序吗？ l1->data 的类型为 int，而不是 node* 类型。

node *tmp = l1->data;

我在这里停止阅读你的代码，因为它没有意义。

正确的代码就是这么简单

void MergeLists(node *l1, node *l2, node *l3) {
    node *l1p = l1->next, *l2p = l2->next, l3p = l3;
    while (l1p != NULL || l2p != NULL) {
        if (l1p != NULL && (l2p == NULL || l1p->data < l2p->data)) {
            l3p->next = malloc(sizeof(node));
            l3p = l3p->next;
            l3p->next = NULL;
            l3p->data = l1p->data;
            l1p = l1p->next;
        } else {
            l3p->next = malloc(sizeof(node));
            l3p = l3p->next;
            l3p->next = NULL;
            l3p->data = l2p->data;
            l2p = l2p->next;
        }
    }
}

此代码假设开始执行函数时l3->next == NULL。