文档章节

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

哭哭吓唬你
 哭哭吓唬你
发布于 2014/04/04 11:23
字数 433
阅读 457
收藏 2


输入:

输入可能包含多个测试样例,输入以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;
}



© 著作权归作者所有

哭哭吓唬你
粉丝 4
博文 101
码字总数 40066
作品 0
石景山
程序员
私信 提问
经典算法学习——合并两个有序链表

类似的,合并两个有序的数组或者链表也是剑指Offer中的经典题型。题目描述如下:输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是按照递增排序的。我这里以合并链表来实现。...

chenyufeng1991
2016/08/21
0
0
LeetCode 23. Merge k Sorted Lists(合并 k 个有序链表)

原题 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 题目: 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。...

dby_freedom
2018/09/27
0
0
Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

题目:Sort List Sort a linked list in O(n log n) time using constant space complexity 看题目有两个要求:1)时间复杂度为O(nlogn);2)空间复杂度为常数,即不能增设额外的空间。 满足...

chambai
2014/10/07
0
0
021-Merge Two Sorted Lists(合并两个排好序的单链表);leetcode

原题   Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 题目大意   合并两个排序链......

quantumcs
2015/10/03
71
0
[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
2018/08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Rust 的 GUI 框架生态概览

本文比较全面比较了目前主流的 Rust 的 GUI 框架的表现。其中 ++ 表示非常好,-- 表示非常差,而 o 表示处于平均水平。 参与对比的框架共有 8 个,详细的比较结果如下: Electron + Neon El...

红薯
26分钟前
3
0
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
3
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
3
0
Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
7
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部