数据结构的基础题,总是不能ac

两个有序链表序列的合并 (20 分)
已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。

输出格式:
在一行中输出合并后新的非降序链表,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。

输入样例:
1 3 5 -1
2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10
这是代码

 #include<stdio.h>
#include<stdlib.h> 
typedef struct ListNode *node;

struct ListNode {
    int num;
    node next;
};

node readlist();
node merge(node s1, node s2 );
node apply();

int main()
{
    node s1,s2,s3;
    s1 = apply();
    s2 = apply();
    s3 = apply();
    s1 = readlist();
    s2 = readlist();
    s3 = merge(s1,s2);

    while(s3!=NULL){
        printf("%d ",s3->num);
        s3=s3->next;
    }
    return 0;
}

node apply()
{
    node L;
    L=(node)malloc(sizeof(struct ListNode));
    L=NULL;
    return L;
}

node readlist()
{
    int n;
    node head,p,last;
    head=last=NULL;
    scanf("%d",&n);
    while(n!=-1){
        p=(node)malloc(sizeof(struct ListNode));
        p->num=n;
        p->next=NULL;
        if(last!=NULL)
        {
            last->next=p;
        }
        else{
            head=p;
        }
        last=p;
        scanf("%d",&n);
    }
    last->next=NULL;
    return head;
} 

node merge(node s1, node s2 )
{
    node s3,Head;
    Head=s3;
    s1=s1->next;
    s2=s2->next;
    while(s1!=NULL&&s2!=NULL){
        if(s1->num>=s2->num){
            s3->next=s2;
            s2=s2->next;
        }
        else{
            s3->next=s1;
            s1=s1->next;
        }
        s3=s3->next;
    }
    if(s1==NULL&&s2==NULL){
        return Head;
    }
    else if(s1!=NULL){
        s3->next=s1;
        return Head;
    }
    else if(s2!=NULL){
        s3->next=s2;
        return Head;
    }
}

1个回答

可以参考一下

 #include "stdio.h"

typedef struct Node
{
    int data;
    struct Node *next;
}Node, *linkList;

void InitList(linkList *L)
{
    (*L) = (linkList)malloc(sizeof(Node));
    (*L)->next = NULL;
}

void creat(linkList L)
{
    Node *s, *r = L;
    int num, flag = 1;
    while(flag)
    {
        scanf("%d", &num);
        if(num >= 0) //num脢脟脪陋虏氓脠毛碌脛脭陋脣脴
        {
            s = (linkList)malloc(sizeof(Node));
            s->data = num;
            r->next = s;
            r = r->next;
        }
        else
        {
            flag = 0;
            r->next = NULL;
        }
    }
}

void print(Node * L)
{
    Node * t = L->next;
    int firstNum = 1;
    if(t == NULL) printf("NULL\n");
    while(t != NULL)
    {
        if(firstNum)
        {
            printf("%d", t->data);
            firstNum = 0;
        }
        else
            printf(" %d", t->data);
        t = t->next;
    }
}

void sort(Node *L1, Node *L2, Node *L3)
{
    Node *s1 = L1->next, *s2 = L2->next;
    Node *r = L3;
    while(s1 != NULL && s2 != NULL)
    {
        if(s1->data < s2->data)
        {
            r->next = s1;
            r = r->next;
            s1 = s1->next;
        }
        else
        {
            r->next = s2;
            r = r->next;
            s2 = s2->next;
        }
    }
    if(s1 != NULL)
        r->next = s1;
    else
        r->next = s2;

    // return s3;
}

int main(int argc, char const *argv[])
{
    Node *L1, *L2, *L3;
    InitList(&L1);
    InitList(&L2);
    InitList(&L3);
    creat(L1);
    creat(L2);
    sort(L1, L2, L3);
    print(L3);
    return 0;
}

你的代码里apply函数是申请空间,但是会导致内存泄漏,比如L申请了空间之后,L指向了堆上的空间,但是接下来L = NULL;就是用NULL覆盖了L的地址值。这样刚才申请的空间首地址就找不到了。
链表如果不是很熟,不建议直接去写合并排序。建议先从简单链表的创建,输出,查询,删除等等,希望对你有帮助!

SUWBS6
SUWBS6 谢谢!
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问