Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

#include <iostream>
using namespace std;

class node{
	public:
		int value;
		node * next;
	
	public:	
		node(int value = 0,node * next = NULL){
			this->value = value;
			this->next = next;
		}
};


int main(int argc, char *argv[]) {
	int m = 0;
	int n = 0;
	while(cin >> m >> n){
		/*建立链表1*/
		node * head_first = new node();
		node * tail_first = head_first;
		for(int i = 0 ; i < m ; i ++){
			node * p = new node();
			int temp;
			cin >> temp;
			p->value = temp;	
			tail_first->next = p;
			tail_first = p;
		}
		/*建立链表2*/
		node * head_second = new node();
		node * tail_second = head_second;
		for(int i = 0 ; i < n ; i ++){
			node * p = new node();
			int temp;
			cin >> temp;
			p->value = temp;
			tail_second->next = p;
			tail_second = p;
		}
		/*输出链表1和2*/
		node * head_1 = head_first->next;
		while(head_1){
			cout << head_1->value << " ";
			head_1 = head_1->next;
		}
		cout << endl;
		node * head_2 = head_second->next;
		while(head_2){
			cout << head_2->value << " ";
			head_2 = head_2->next;
		}
		cout << endl;
		
		/*归并链表*/
		head_1 = head_first->next;
		head_2 = head_second->next;
		node * head = new node();
		node * tail = head;
		while(head_1&&head_2){
			node * q = new node();
			if(head_1->value <= head_2->value){
				q->value = head_1->value;
				head_1 = head_1->next;
			}
			else{
				q->value = head_2->value;
				head_2 = head_2->next;
			}
			tail->next = q;
			tail = q;
			
		}
		while(head_1){
			node * q = new node(head_1->value);
			tail->next = q;
			tail = q;
			head_1 = head_1->next;
		}
		while(head_2){
			node * q = new node(head_2->value);
			tail->next = q;
			tail = q;
			head_2 = head_2->next;
		}
		/*输出新链表*/
		node * p = head->next;
		while(p){
			cout << p->value << " ";
			p = p->next;
		}
		cout << endl;
		
	}
}