419
技術社區[雲棲]
劍指Offer之合並兩個排序的鏈表
- 題目描述：
-
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成後的鏈表，當然我們需要合成後的鏈表滿足單調不減規則。
(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：合並兩個排序的鏈表
* 來源：https://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：合並兩個排序的鏈表
* 來源：https://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;
}
最後更新：2017-04-03 14:54:27