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

我正在写一个void函数void merged_lists（cell * l1，cell * l2，cell * l3）;谁收到两个以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->空

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。

在开始时如何解决此问题的任何技巧？

（我知道我之前曾发布过类似的问题，但是随着重点的改变，我认为再次发表这篇文章是公平的）

最佳答案

此代码有第一个问题

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

您用l3或l2的值覆盖l1。结果是内存泄漏，因为所引用的头节点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;
}

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

另一个问题在else块中。同样，您将覆盖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。

关于c - 将已排序的链表与头节点合并，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60068589/

L3

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