第九章(二)第四题

题目要求

本题要求实现一个合并两个有序链表的简单函数。链表结点定义如下:
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 (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,*p1,*p2,*p;
    p1=list1;
    p2=list2;
    if(list1==NULL&&list2==NULL)//若两个链表都是空链表,则返回空指针
        return NULL;
    else
    {
        if( p1->data <= p2->data )//若链表一的第一个值小于等于链表二的第一个值
        {
            head=p1;//使头指针指向链表一
            p1=p1->next;//链表一向后顺延
            p=head;//使p指向头指针
        }
        else//反之亦然
        {
            head=p2;
            p2=p2->next;
            p=head;
        }
        while(p1!=NULL&&p2!=NULL)//当两个链表没有到达最后一个结点时开始循环
        {
            if(p1->data<=p2->data)//判断大小关系,将大的连接到小的后面
            {
                p->next=p1;
                p=p1;
                p1=p1->next;
            }
            else
            {
                p->next=p2;
                p=p2;
                p2=p2->next;
            }
        }
        if(p1==NULL)//判断哪个链表为空,将不为空的链表连接到所生成链表的后面
        {
            p->next=p2;
        }
        if(p2==NULL)
        {
            p->next=p1;
        }
    }
    return head;//返回头指针
}

裁判函数补全:

struct ListNode *createlist()//输入函数
{
    struct ListNode *head= (struct ListNode*)malloc(sizeof(struct ListNode));//建立头结点
    struct ListNode *temp;//建立一个指针使其指向头结点
    temp=head;
    do
    {
        struct ListNode *a = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟内存空间
        scanf("%d", &a->data);//输入数据
        if (a->data == -1)//如果输入的数据是-1,跳出循环
            break;
        a->next = NULL;//使next置空
        temp->next = a;//使temp指针指向a
        temp = temp->next;//等价于temp=a
    } while (temp->data != -1);
    return head->next;//返回其首元结点的地址
}

注意事项:

1.本题中createlist函数返回的是首元结点的地址而不是头结点的地址。

2.看完了点个赞吧,谢谢宁辣.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容