題目1519：合并兩個排序的連結清單-九度

題目描述：

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

(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

推薦指數：※

來源：http://ac.jobdu.com/problem.php?pid=1519

合并兩個連結清單，在掃描過程中，操作節點，兩個link合并到link1中。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct node{
    int val;
    node * next;
}node;
void input_link(node *head ,int len){
    node *pre=head;
    for(int i=0;i<len;i++){
        node *nnode=new node;
        nnode->next=NULL;
        scanf("%d",&nnode->val);
        pre->next=nnode;
        pre=nnode;
    }
}
node*  merge_link(node *head1,node *head2){
    node *p1=head1->next;
    node *pre1=head1;
    node *p2=head2->next;
    while(p1!=NULL&&p2!=NULL){
		if(p1->val<p2->val){
			pre1=p1;
			p1=p1->next;
		}
		else{
			node *q=p2->next;//store 
			p2->next=p1;//insert
			pre1->next=p2;//link
			pre1=p2;//finish
			p2=q;
		}
    }
	if(p2!=NULL)
		pre1->next=p2;
    return head1;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        node *head1=new node;
        node *head2=new node;
		head1->next=NULL;
		head2->next=NULL;
        input_link(head1,n);
        input_link(head2,m);
        node * p=merge_link(head1,head2);
        p=p->next;
        if(p!=NULL){
            printf("%d",p->val);
			while(p->next!=NULL){
				p=p->next;
				printf(" %d",p->val);
			}
		}
		else
			printf("NULL");
        printf("\n");
    }
    return 0;
}
           

海濤的遞歸算法。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef struct node{
    int val;
    node * next;
}node;
void input_link(node *head ,int len){
    node *pre=head;
    for(int i=0;i<len;i++){
        node *nnode=new node;
        nnode->next=NULL;
        scanf("%d",&nnode->val);
        pre->next=nnode;
        pre=nnode;
    }
}
node*  merge_link(node *head1,node *head2){
    if(head1==NULL)
        return head2;
    else if(head2==NULL)
        return head1;
    node *p=NULL;
    if(head1->val<head2->val){
        p=head1;
        p->next=merge_link(head1->next,head2);
    }
    else{
        p=head2;
        p->next=merge_link(head1,head2->next);
    }
    return p;
    
}


int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        node *head1=new node;
        node *head2=new node; 
        input_link(head1,n);
        input_link(head2,m);
        node *p= merge_link(head1->next,head2->next);
        if(p!=NULL){
            printf("%d",p->val);
            while(p->next!=NULL){
                p=p->next;
                printf(" %d",p->val);
            } 
        }
        else
            printf("NULL");
        printf("\n");
    }
    return 0;
}