剑指OFFER之合并有序链表(九度OJ1519)

题目描述:

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 (hint: 请务必使用链表。)

输入:

输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行为两个整数n和m(0<=n<=1000, 0<=m<=1000):n代表将要输入的第一个链表的元素的个数,m代表将要输入的第二个链表的元素的个数。 下面一行包括n个数t(1<=t<=1000000):代表链表一中的元素。接下来一行包含m个元素,s(1<=t<=1000000)。

输出:

对应每个测试案例, 若有结果,输出相应的链表。否则,输出NULL。

样例输入:

5 2
1 3 5 7 9
2 4
0 0

样例输出:

1 2 3 4 5 7 9
NULL

解题思路:

  首先给定了两个有序的链表,那么可以考虑使用三个指针,p1指向链表1,p2指向链表2,p3指向合并后的链表3.那么依次扫描链表1和2,每次把小的元素放到p3的后面,p3再指向链表3的尾巴。最后要仔细考虑的问题:  1 如果两个链表都为空

if(n1 == 0 && n2 == 0)
            printf("NULL\n");

  2 如果其中一个链表为空

    if(head1->next == NULL){
        res->next = head2->next;
        return ;
    }
    if(head2->next == NULL){
        res->next = head1->next;
        return ;
    }

  3 如果一个链表提前扫描完

        Node *p1;
    Node *p2;
    Node *p3 = res;
    while(head1->next != NULL && head2->next != NULL){
        p1 = head1->next;
        p2 = head2->next;
        if(p1->number < p2->number){
            head1->next = p1->next;
            p1->next = p3->next;
            p3->next = p1;
            p3 = p3->next;
        }else{
            head2->next = p2->next;
            p2->next = p3->next;
            p3->next = p2;
            p3 = p3->next;
        }
    }
    if(head1->next == NULL)
        p3->next = head2->next;
    if(head2->next == NULL)
        p3->next = head1->next;    

  解决了这三个问题,就完成了链表的排序。

代码:

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int number;
    struct node * next;
}Node;
void mergeList(Node *res,Node *head1,Node *head2);
int main(){
    int n1,n2;
    int i;
    int temp;
    while(scanf("%d %d",&n1,&n2)!=EOF && n1>=0 && n1<=1000 && n2>=0 && n2<=1000){
        Node *head1 = (Node *)malloc(sizeof(Node));
        Node *head2 = (Node *)malloc(sizeof(Node));
        head1->next = NULL;
        head2->next = NULL;
        Node *tail1 = head1;
        Node *tail2 = head2;
        for(i=0;i<n1;i++){
            scanf("%d",&temp);
            Node *p = (Node *)malloc(sizeof(Node));
            p->next = tail1->next;
            tail1->next = p;
            p->number = temp;
            tail1 = tail1->next;
        }
        for(i=0;i<n2;i++){
            scanf("%d",&temp);
            Node *p = (Node *)malloc(sizeof(Node));
            p->next = tail2->next;
            tail2->next = p;
            p->number = temp;
            tail2 = tail2->next;
        }
        Node *res = (Node *)malloc(sizeof(Node));
        mergeList(res,head1,head2);
        if(n1 == 0 && n2 == 0)
            printf("NULL\n");
        else{
            Node *p = res->next;
            printf("%d",p->number);
            p = p->next;
            while(p != NULL){
                printf(" %d",p->number);
                p = p->next;
            }
            printf("\n");
        }
    }
    return 0;
}
void mergeList(Node *res,Node *head1,Node *head2){
    if(head1->next == NULL){
        res->next = head2->next;
        return ;
    }
    if(head2->next == NULL){
        res->next = head1->next;
        return ;
    }
    Node *p1;
    Node *p2;
    Node *p3 = res;
    while(head1->next != NULL && head2->next != NULL){
        p1 = head1->next;
        p2 = head2->next;
        if(p1->number < p2->number){
            head1->next = p1->next;
            p1->next = p3->next;
            p3->next = p1;
            p3 = p3->next;
        }else{
            head2->next = p2->next;
            p2->next = p3->next;
            p3->next = p2;
            p3 = p3->next;
        }
    }
    if(head1->next == NULL)
        p3->next = head2->next;
    if(head2->next == NULL)
        p3->next = head1->next;
    return ;
}
/**************************************************************
    Problem: 1519
    User: xhalo
    Language: C
    Result: Accepted
    Time:250 ms
    Memory:4212 kb
****************************************************************/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MelonTeam专栏

浅析Associated Object

Category是Objective C为程序员提供的一个强大的动态机制,它们允许程序员为已有的对象添加新的方法,即便是在没有该对象的源代码的情况下。通过它可以...

239100
来自专栏JavaEE

mybatis笔记整理mybatis的基本用法及配置:

414110
来自专栏企鹅号快讯

谈谈 MySQL 隐式类型转换

来源:andyqian www.andyqian.com/2017/11/11/database/MySQLConvert/ 前言 今天我们继续回到MySQL系...

512110
来自专栏CodingToDie

MySql Hash 索引

Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 ...

32930
来自专栏C#

奇妙的NULL值,你知道多少

《NULL值的多义性分析》       谈到NULL值,很多人都是很熟悉,但是深入了解后,又感觉到陌生,对其含义和用法,都无法很准确的理解。NULL在数据库和...

23050
来自专栏IT杂记

Mapreduce程序中reduce的Iterable参数迭代出是同一个对象

今天在对reduce的参数Iterable进行迭代时,发现一个问题,即Iterator的next()方法每次返回的是同一个对象,next()只是修改了Writa...

21050
来自专栏nnngu

算法07 五大查找之:索引查找

上一篇总结了二分查找,这一篇要总结的是索引查找。 关于索引,我们很容易地联想到数据库中的索引,建立了索引,可以大大提高数据库的查询速度。 索引查找又称为分块查找...

43560
来自专栏吴伟祥

自定义template(Settings-->Live Templates)

psvm=public static void main(String[] args) {}

9720
来自专栏Laoqi's Linux运维专列

SQLAlchemy总结+

39130
来自专栏Java成神之路

PL/SQL学习笔记_01_基础:变量、流程控制

PL/SQL语句可以在Oracle客户端的 SQL窗口或者 command  窗口中运行

11920

扫码关注云+社区

领取腾讯云代金券