题目描述:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
(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
/*********************************
* 日期:2013-11-23
* 作者:SJF0115
* 题号: 题目1519:合并两个排序的链表
* 来源:http://ac.jobdu.com/problem.php?pid=1519
* 结果:AC
* 来源:剑指Offer
* 总结:
**********************************/
#include<iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;
typedef struct ListNode{
int value;
struct ListNode* next;
}ListNode;
//打印链表
void OutPut(ListNode*head){
if(head == NULL){
printf("NULL\n");
}
else{
ListNode *p;
p = head->next;
while(p != NULL){
//如果是最一个
if(p->next == NULL){
printf("%d\n",p->value);
}
else{
printf("%d ",p->value);
}
p = p->next;
}
}
}
//创建链表
ListNode* CreateList(ListNode *head,int n){
ListNode *newNode,*p;
p = head;
for(int i = 0;i < n;i++){
newNode = (ListNode*)malloc(sizeof(ListNode));
scanf("%d",&newNode->value);
newNode->next = NULL;
p->next = newNode;
p = newNode;
}
return head;
}
ListNode* Merge(ListNode*head1,ListNode*head2){
//head1,head2带有头结点
if(head1->next == NULL && head2->next == NULL){
return NULL;
}
//只有第一个字符串,无需合并,直接输出
else if(head2->next == NULL){
return head1;
}
//只有第二个字符串,无需合并,直接输出
else if(head1->next == NULL){
return head2;
}
//合并
else{
ListNode *p1,*p2,*p3,*head;
head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
p1 = head1->next;
p2 = head2->next;
p3 = head;
while(p1 != NULL && p2 != NULL){
if(p1->value < p2->value){
p3->next = p1;
p1 = p1->next;
}
else{
p3->next = p2;
p2 = p2->next;
}
p3 = p3->next;
}
//head1没有遍历完
while(p1 != NULL){
p3->next = p1;
p1 = p1->next;
p3 = p3->next;
}
//head2没有遍历完
while(p2 != NULL){
p3->next = p2;
p2 = p2->next;
p3 = p3->next;
}
return head;
}
}
int main() {
int i,n,m;
while(scanf("%d %d",&n,&m) != EOF){
ListNode *head1,*head2;
head1 = (ListNode*)malloc(sizeof(ListNode));
head2 = (ListNode*)malloc(sizeof(ListNode));
head1->next = NULL;
head2->next = NULL;
//创建链表
if(n != 0){
head1 = CreateList(head1,n);
}
if(m != 0){
head2 = CreateList(head2,m);
}
//合并排序
head1 = Merge(head1,head2);
//打印链表
if(head1 == NULL){
printf("NULL\n");
}
else{
OutPut(head1);
}
}//while
return 0;
}
【方法二】
【解析】
【代码】
/*********************************
* 日期:2013-11-23
* 作者:SJF0115
* 题号: 题目1519:合并两个排序的链表
* 来源:http://ac.jobdu.com/problem.php?pid=1519
* 结果:AC
* 来源:剑指Offer
* 总结:
**********************************/
#include<iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;
typedef struct ListNode{
int value;
struct ListNode* next;
}ListNode;
//打印链表
void OutPut(ListNode*head){
if(head == NULL){
printf("NULL\n");
}
else{
ListNode *p;
p = head;
while(p != NULL){
//如果是最一个
if(p->next == NULL){
printf("%d\n",p->value);
}
else{
printf("%d ",p->value);
}
p = p->next;
}
}
}
//创建链表
ListNode* CreateList(ListNode *head,int n){
ListNode *newNode,*p;
p = head;
for(int i = 0;i < n;i++){
newNode = (ListNode*)malloc(sizeof(ListNode));
scanf("%d",&newNode->value);
newNode->next = NULL;
p->next = newNode;
p = newNode;
}
return head;
}
//递归
ListNode* Merge(ListNode*head1,ListNode*head2){
if(head1 == NULL && head2 == NULL){
return NULL;
}
else if(head2 == NULL){
return head1;
}
else if(head1 == NULL){
return head2;
}
//合并
ListNode *head = NULL;
if(head1->value < head2->value){
head = head1;
head->next = Merge(head1->next,head2);
}
else{
head = head2;
head->next = Merge(head1,head2->next);
}
return head;
}
int main() {
int i,n,m;
while(scanf("%d %d",&n,&m) != EOF){
ListNode *head1,*head2;
head1 = (ListNode*)malloc(sizeof(ListNode));
head2 = (ListNode*)malloc(sizeof(ListNode));
head1->next = NULL;
head2->next = NULL;
//创建链表
if(n != 0){
head1 = CreateList(head1,n);
}
if(m != 0){
head2 = CreateList(head2,m);
}
//合并排序
head1 = Merge(head1->next,head2->next);
//打印链表
if(head1 == NULL){
printf("NULL\n");
}
else{
OutPut(head1);
}
}//while
return 0;
}
分享到:
相关推荐
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
题目描述 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 原创文章 264获赞 692访问量 3万+ 关注 私信 展开阅读全文 作者:程旭员
1.对两个链表,比较它们的头节点,头节点小的即为合并之链表后的头节点 2.对与剩下的链表,比较他们的头节点,然后将头节点小的与之前合并链表的尾部连接起来 3.重
17. 合并两个有序链表 18. 判断二叉树A中是否包含子树B 19. 二叉树的镜像 20. 顺时针打印矩阵 21. 包含min函数的栈 22. 判断一个栈是否是另一个栈的弹出序列 23. 层序遍历二叉树 24. 后序遍历二叉搜索树 25. ...
剑指offer:合并两个排序的链表,Python实现 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 吐槽 本来想用递归实现,但是大脑卡壳,没有想到合适的递归...
【Python学习-链表】【剑指offer】之链表中倒数第k个结点、反转链表、合并排序链表题目分析代码反转链表分析代码合并排序链表分析代码 题目 输入一个链表,输出该链表中倒数第k个结点。 分析 方法一:先计数,在查询...
题目:合并两个排序的链表 题:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 解题思路一:递归,并需注意对空链表单独处理。 class Solution: # 返回合并后...
翻转单词顺序列,反转链表,斐波那契数列,复杂链表的复制,构建乘积数组,和为s的连续整数序列,和为s的两个数字,滑动窗口的最大值,机器人的运动范围,剑指offer-python实现.docx,矩形覆盖,矩阵中的路径,连续子数组的最大...
面试题17 合并两个排序的链表 面试题18 树的子结构 第4章 解决面试题思路 4.2 画图让抽象问题形象化 面试题19 二叉树的镜像 面试题20 顺时针打印矩阵 4.3 举例让抽象问题具体化 面试题21 包含min函数的栈 面试题22 ...
leetcode中文版 jianzhi-Offer-Leetcode 《剑指Offer》与Leetcode主站题目链接对应 update:中文版leetcode已发布剑指offer授权的刷题合集: ...√合并两个排序的链表 -> √树的子结构 -> * √二叉树
leetcode ...合并两个排序的链表 代码的鲁棒性 17 树的子结构 代码的鲁棒性 18 二叉树的镜像 面试思路 19 顺时针打印矩阵 画图让抽象形象化 LeetCode 54 20 包含min函数的栈 举例让抽象具体化 21 栈
Leetcode扑克 剑指offer-Java题解 二维数组中的查找 - [行列递增的二维数组搜索]- leetcode 240 替换空格 从尾到头打印链表 ...合并两个排序的链表 - [合并两个有序链表]- leetcode 21 树的子结构 -
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...
面试题25:合并两个排序的链表 面试题35:复杂链表的复制(深拷贝、浅拷贝,分解复杂问题,遍历链表时的边界条件(用node.next当条件遍历时最后一个节点不会被遍历到),复制不要修改原对象) 面试题36:二叉搜索树...
17合并两个排序的链表 18树的子结构 19二叉树的镜像 20顺时针打印矩阵 21包含min函数的栈 22栈的压入弹出序列 23从上往下打印二叉树 24二叉搜索树的后序遍历序列 25二叉树中和为某一值的路径 26复杂链表的复制 27...
合并两个有序链表 简单 0026 删除排序数组中的重复项 简单 0027 移除元素 简单 0028 实现 strStr() 简单 下一个排列 中等 在排序数组中查找元素的第一个和最后一个位置 中等 0035 搜索插入位置 简单 0038 外观数列 ...
leetcode和剑指 Algorithm Algorithm for Sword Finger,leetcode,acm....so ...16.单链表:合并两个排序的链表 17.二叉树:树的子结构 18.二叉树:二叉树的镜像 19.顺时针打印矩阵 20.栈:包含min函数的栈
4、合并两个有序链表 5、删除链表倒数第 n 个结点 6、求单向链表的中间结点 二、栈 1、Java实现顺序栈、链式栈 三、队列 1、顺序队列、链式队列 2、循环队列 四、排序算法 1、冒泡排序 2、插入排序 3、选择排序 4、...
leetcode 答案 leetcode刷题分类基础(前端JavaScript版答案) [TOC] ...25.合并两个排序的链表 5、focus 52. 两个链表的第一个公共节点 五 DFS深度优先搜索 1、(递归)27. 二叉树的镜像 2、28. 对
16.合并两个排序的链表 题目: 答案: 18.二叉树的镜像 题目: 答案: 36.两个链表的第一个公共结点 题目: 答案: 38.二叉树的深度 题目: 答案: 39.平衡二叉树 题目: 答案: 分类 删除链表的节点 题目: 答案: