数据结构两个有序链表拼接一个有序链表

Question

链表的拼接：两个有序链表拼接成一个有序链表
这个指针p为什么只开辟了一次空间啊，不明白

     struct ListNode mergelists(struct ListNode *listl， struct ListNode *list2）                                                                                                                                     复制
 2
 3          struct ListNode *head=NULL
 4          struct ListNode *p=NULL
 5         p=（struct ListNode*)malloc（sizeof(struct ListNode））//不懂
          head=pi
 8         while（list1!=NULL&&1ist2！=NULL）
 9              if(list1->data<list2->data）{
 10                    p->next=1ist1;
 11                    list1=list1->next;
 12                    p=p->next;
 13                Telsef
 14                    p->next         =1ist2;
 5                    list2=1ist2->next;
 16                    p=p->next;
 7
 18
 19           if(list1!=NULL)p->next=list1;
 20           if(list2!=NULL）p->next=list2
 21           head=head->next;
 22           return head:
 23

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); /*裁判实现，细节不表*/
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode  *list1, *list2;

    list1 = createlist();
    list2 = createlist();
    list1 = mergelists(list1, list2);
    printlist(list1);
    
    return 0;
}

/* 你的代码将被嵌在这里 */
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
    struct ListNode *head=NULL;
    struct ListNode *p=NULL;
    p = (struct ListNode*)malloc(sizeof(struct ListNode));//不懂
    head =p;
    
    while(list1!=NULL && list2!=NULL){
        if(list1->data < list2->data){
            p->next = list1;
            list1= list1->next;
            p = p->next;
        }else{
            p->next = list2;
            list2= list2->next;
            p = p->next;
        }
    }
    if(list1!=NULL) p->next = list1;
    if(list2!=NULL) p->next = list2;
    head = head->next;
    return head;
}

Answer 1

【以下回答由 GPT 生成】

这段代码的逻辑是正确的，它将两个有序链表拼接成一个有序链表。但是，我发现了一些可以进行优化的地方。下面是针对这段代码的优化建议和解决方案：

1. 不需要为头节点head和指针p分别分配内存，并将head指向p。可以只使用一个指针p，并在循环结束后将p返回即可。

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2) {
    struct ListNode *p = NULL;
    struct ListNode *head = NULL;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data < list2->data) {
            if (head == NULL) {  // 当head为空时，将p指向较小的节点作为头节点
                head = p = list1;
            } else {
                p->next = list1;
                p = p->next;
            }
            list1 = list1->next;
        } else {
            if (head == NULL) {  // 当head为空时，将p指向较小的节点作为头节点
                head = p = list2;
            } else {
                p->next = list2;
                p = p->next;
            }
            list2 = list2->next;
        }
    }

    if (list1 != NULL)  // 拼接剩余的节点
        p->next = list1;

    if (list2 != NULL)
        p->next = list2;

    return head;
}

1. 可以考虑使用递归来实现拼接操作，简化代码。递归的思想是将两个链表头节点较小的节点作为拼接后的链表的头节点，然后再递归地拼接两个链表剩余的部分。

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2) {
    if (list1 == NULL)
        return list2;

    if (list2 == NULL)
        return list1;

    if (list1->data < list2->data) {
        list1->next = mergelists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergelists(list1, list2->next);
        return list2;
    }
}

这种递归的解法更简洁，但是需要注意，如果链表长度非常大，递归可能会导致栈溢出的问题。因此，需要根据实际情况来选择使用递归还是迭代。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7578019
• 这篇博客你也可以参考下：交换P所指结点与其下一个结点的位置
• 除此之外, 这篇博客: 数据结构：双链表的创建以及以P结点为基准的结点插入和删除中的 链表初始化 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^