剑指Offer - 九度1519 - 合并两个排序的链表

剑指Offer - 九度1519 - 合并两个排序的链表
2013-11-30 22:04
题目描述:

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
(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
题意分析:
  合并链表,面试必考的题目。写的时候以下三个原则:
    1. NULL一定要检查到位,否则会被鄙视
    2. 合并链表要把原链表的节点拼成一条,而不是new出一堆新的节点,否则会被严重鄙视
    3. 可以new出一个节点指向表头,这样能省点代码量。但对于频繁调用的函数,一次多余的new、delete都不应该有。
  下面是ac的代码,当时写的时候貌似偷懒了...,第三条没做到。时间复杂度O(m + n),空间复杂度O(1)。
 // 651961    zhuli19901106    1519    Accepted    点击此处查看所有case的执行结果    1024KB    1802B    230MS
//
#include <cstdio>
using namespace std; struct Node{
int val;
struct Node *next;
Node(int _val = ): val(_val), next(NULL){}
}; int main()
{
int n, m;
int i, tmp;
struct Node *h1, *h2, *h3;
struct Node *p1, *p2, *p3;
struct Node *r1, *r2, *r3; while(scanf("%d%d", &n, &m) == ){
if(n <= && m <= ){
printf("NULL\n");
continue;
}
r1 = new Node();
r2 = new Node();
r3 = new Node(); p1 = r1;
for(i = ; i < n; ++i){
scanf("%d", &tmp);
p1->next = new Node(tmp);
p1 = p1->next;
}
h1 = r1->next; p2 = r2;
for(i = ; i < m; ++i){
scanf("%d", &tmp);
p2->next = new Node(tmp);
p2 = p2->next;
}
h2 = r2->next; p3 = r3;
while(h1 != NULL && h2 != NULL){
if(h1->val < h2->val){
p1 = h1->next;
p3->next = h1;
p3 = p3->next;
p3->next = NULL;
h1 = p1;
}else{
p2 = h2->next;
p3->next = h2;
p3 = p3->next;
p3->next = NULL;
h2 = p2;
}
} while(h1 != NULL){
p1 = h1->next;
p3->next = h1;
p3 = p3->next;
p3->next = NULL;
h1 = p1;
} while(h2 != NULL){
p2 = h2->next;
p3->next = h2;
p3 = p3->next;
p3->next = NULL;
h2 = p2;
} h3 = r3->next;
printf("%d", h3->val);
p3 = h3->next;
while(p3 != NULL){
printf(" %d", p3->val);
p3 = p3->next;
}
printf("\n"); while(r3->next != NULL){
p3 = r3->next;
r3->next = p3->next;
delete p3;
} delete r1;
delete r2;
delete r3;
r1 = r2 = r3 = NULL;
} return ;
}
上一篇:Tomcat发布项目方法


下一篇:配置开发支持高并发TCP连接的Linux应用程序全攻略