题目1519:合并两个排序的链表

原创
2014/04/04 11:23
阅读数 500


输入:

输入可能包含多个测试样例,输入以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
#include <iostream>
using namespace std;
struct Node {
	int data;
	Node* next;

	Node(int data) {
		this->data = data;
		this->next = NULL;
	}

	Node() {
		this->data = 0;
		this->next = NULL;
	}
};
int main() {

	int n, m;
	while (cin >> n >> m) {
		if(n==0 && m == 0){
			cout<<"NULL"<<endl;
		}else{

			Node* fHead = new Node;
			cin >> fHead->data;
			Node* node = NULL;
			Node* fP = fHead;
			for (int i = 1; i < n; i++) {
				node = new Node();
				cin >> node->data;
				fP->next = node;
				fP = node;
			}

			Node* sHead = new Node;
			Node* sP = sHead;
			cin >> sHead->data;
			for (int i = 1; i < m; i++) {
				node = new Node;
				cin >> node->data;
				sP->next = node;
				sP = node;
			}

			sP = sHead;
			fP = fHead;
			Node* fPost = NULL;
			Node* sPost = NULL;

			Node* result = new Node;
			Node* rP = result;
			while (fP && sP) {
				fPost = fP->next;
				sPost = sP->next;

				if (fP->data <= sP->data) {
					fP->next = NULL;
					rP->next = fP;
					rP = fP;
					fP = fPost;
				} else {
					sP->next = NULL;
					rP->next = sP;
					rP = sP;
					sP = sPost;
				}
			}

			if (fP) {
				rP->next = fP;
			}
			if (sP) {
				rP->next = sP;
			}

			rP = result->next;
			for (int i = 0; i < (m + n - 1); i++) {
				cout << rP->data << " ";
				rP = rP->next;
			}
			cout << rP->data << endl;
		}
	}
	return 0;
}



展开阅读全文
打赏
0
2 收藏
分享
加载中
更多评论
打赏
0 评论
2 收藏
0
分享
返回顶部
顶部