2206: 最快合并链表(线性表)

题目描述

知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。

输入

m=5
3 6 1 3 5
n=4.
7 10 8 4

输出

3 6 1 3 5 7 10 8 4

样例输入

m=7
3 5 1 3 4 6 0

n=5

5 4 8 9 5

样例输出

3 5 1 3 4 6 0 5 4 8 9 5 

参考代码

#include"stdio.h"
#include"stdlib.h"
struct node 
{
    int date;
    struct node *next;
    struct node *pre;
}
;
struct node *creat(struct node *head,int t) 
{
    struct node *p1=NULL,*p2=NULL;
    int i;
    for (i=1;i<=t;i++) 
    {
        p1=(struct node*)malloc(sizeof(struct node));
        scanf("%d",&p1->date);
        p1->pre=p1->next=NULL;
        if(i==1)
                    head=p1;
        if(i!=1) 
        {
            p2->next=p1;
            p1->pre=p2;
        }
        p2=p1;
    }
    p1->next=0;
    return head;
}
struct node *Union(struct node *L1,struct node *L2) 
{
    struct node *p1=L1,*p2=0;
    while(p1->next!=0)
            p1=p1->next;
    p2=p1;
    p2->next=L2;
    L2->pre=p2;
    p1=L2;
    while(p1->next!=0)
            p1=p1->next;
    p1->next=L1;
    L1->pre=p1;
    return L1;
}
int main() 
{
    struct node *L1=0,*L2=0,*temp;
    int m,n,i,t=0;
    char c1,c2;
    scanf("%c=%d",&c1,&m);
    L1=creat(L1,m);
    while(scanf("%c",&c1)) 
    {
        if(c1=='n')
                    break;
    }
    scanf("=%d",&n);
    L2=creat(L2,n);
    temp=Union(L1,L2);
    while(1) 
    {
        printf("%d",temp->date);
        t++;
        if(t!=m+n)
                    printf(" "); else
                    break;
        temp=temp->next;
    }
    return 0;
}

解析

暂无