2-3 链表拼接 (20 分)

2-3 链表拼接 (20 分)
本题要求实现一个合并两个有序链表的简单函数。链表结点定义如下:

struct ListNode {
int data;
struct ListNode *next;
};
函数接口定义:
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);
其中list1和list2是用户传入的两个按data升序链接的链表的头指针;函数mergelists将两个链表合并成一个按data升序链接的链表,并返回结果链表的头指针。

裁判测试程序样例:
#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 § {
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;

}

/* 你的代码将被嵌在这里 */
输入样例:
1 3 5 7 -1
2 4 6 -1
结尾无空行
输出样例:
1 2 3 4 5 6 7
这道题的思想就是创建一个新链表,采用尾插法的方式,将两个表中较小的元素插入新表中,最后剩下的再单独插入,也可以采用头插法,选表中较大的元素插入新表,这样最小的仍然在最前面

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

struct ListNode{
int data;
struct ListNode*next;
};
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
    struct ListNode *L,*s,*r;
    L=NULL;
    r=L;
    while(list1!=NULL&&list2!=NULL)
    {
    if((list1->data<list2->data)||(list1->data==list2->data))
    {
        s=(struct ListNode*)malloc(sizeof(struct ListNode));
        s->data=list1->data;
        if(L==NULL)L=s;
        else
        {
            r->next=s;
        }
         r=s;
        if(r!=NULL)
            r->next=NULL;
            list1=list1->next;
    }
    else if(list1->data>list2->data)
    {
        s=(struct ListNode*)malloc(sizeof(struct ListNode));
        s->data=list2->data;
        if(L==NULL)L=s;
        else
        {
            r->next=s;
        }
          r=s;
        if(r!=NULL)
            r->next=NULL;
            list2=list2->next;
    }
    }
    if(list2!=NULL)
        list1=list2;
    while(list1!=NULL)
    {
        s=(struct ListNode*)malloc(sizeof(struct ListNode));
        s->data=list1->data;
        if(L==NULL)L=s;
        else
        {
            r->next=s;
        }
         r=s;
        if(r!=NULL)
            r->next=NULL;
            list1=list1->next;
    }
    return L;

};
struct ListNode *createlist();
struct ListNode *createlist()
{
    struct ListNode *L,*s,*r;
    L=NULL;
    r=L;
    int x;
    scanf("%d",&x);
    while(x!=-1)
    {
        s=(struct ListNode*)malloc(sizeof(struct ListNode));
        s->data=x;
        if(L==NULL)L=s;
        else
            r->next=s;
        r=s;
        scanf("%d",&x);
    }
    if(r!=NULL)r->next=NULL;
    return L;
};
void printlist( struct ListNode *head );
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;
}

上一篇:java Stream快速入门01


下一篇:实现自己的框架