http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=316#problem/B
这道题我用的方法是改变每个结点的指针域并从小到大排列,每次记录新链表最后一个结点的地址从而实现链表合并并降序输出

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int data;
    struct node *next;
}Node;
//创建链表,此处创建的是无头结点的链表
Node *create(){
    int i,j;
    Node *head,*p,*q;
    head=NULL;
    scanf("%d",&j);
    while(j){
        –j;//j的位置将影响到输入的数据是否要多输一个,而放在这里无影响
        scanf("%d", &i);
        p=(Node *)malloc(sizeof(Node));
        p->data=i;
        if(head==NULL)
        q=head=p;
        else
            q->next=p;
        q=p;
    }
    p->next=NULL;
    return head;
}
//输出链表
void print(Node *head){//打出的链表将是第一个结点为c的新链表
    Node *p;
    p=head;
    while(p){    
    printf("%d ",p->data);
    p=p->next;
    }
}
//链表合并
Node *list(Node *head,Node *head1){  //通过改变指针的指向形成新链表
    Node *t,*c=NULL;//c所处的位置永远是新链表的最后一个结点
    while((head!=NULL)&&(head1!=NULL)){
        if(head->data>=head1->data){ //通过两结点数据域大小判断放入前端的点
            t=head1;
            head1=head1->next;//移动至下一位
        }
        else{
            t=head;
            head=head->next;//移动至下一位
        }
        t->next=c;//存倒数第二个结点,第一次循环后为NULL,即第一个结点
        c=t;
    }
    if(head!=NULL)    //若head1到最后则将head后的全部元素连到新链表中
        while(head!=NULL){
            t=head;
            head=head->next;
            t->next=c;
            c=t;
        }
    else     //若head到最后则将head1后的全部元素连到新链表中
 
        while(head1!=NULL){
            t=head1;
            head1=head1->next;
            t->next=c;
            c=t;
        }
    return c;//最终新链表将以升序排列但c对应第一个结点
}
int main(){
    Node *head,*head1,*head2;//head2储存已合并的链表
    head=create();
    head1=create();
    head2=list(head,head1);
    print(head2);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation