微软面试100题系列：一道合并链表问题的解答[第42题]
微软面试100题V0.1版第42题合并链表解答
July、网友二零一一年一月2日
------------------------------------
本文参考：本人整理的微软面试100题系列V0.1版第42题、网友的回复。
本人声明：本人对此微软等100题系列任何资料享有版权。
由于微软等面试100题系列的答案V0.2版，答案V0.3版[第1-40题答案]都已经放出，
而答案V0.3版最近新整理好，在上传之前，选择性的贴几道题的答案，以让读者检验。
至于第1-40题的答案，日后，我也会不定期的选择性的在我博客里一一阐述。
ok，第56题[最长公共子序列]的答案，已在我的博文：
24个经典算法系列：3、动态规划算法解微软面试第56题 中明确阐述了。
这次，咱们来看一道链表合并的面试题。
42、请修改append函数，利用这个函数实现：两个非降序链表的并集，
1->2->3 和 2->3->5 并为 1->2->3->5另外只能输出结果，不能修改两个链表的数据。
此题，合并链表，要求将俩个非有序排列的链表，有顺序的合并。如下：
//程序一、引自一网友。
#include <stdio.h>
#include <malloc.h>
typedef struct lnode {
int data;
struct lnode *next;
}lnode,*linklist;
linklist creatlist(int m)//创建链表
{
linklist p,l,s;
int i;
p=l=(linklist)malloc(sizeof(lnode));
p->next=NULL;
printf("请输入链表中的一个数字：");
scanf("%d",&p->data);
for(i=2;i<=m;i++)
{
s=(linklist)malloc(sizeof(lnode));
s->next = NULL;
printf("请输入第%d个数字",i);
scanf("%d",&s->data);
p->next=s;
p=p->next;
}
printf("\n");
return l;
}
void print(linklist h)//打印链表
{
linklist p=h->next;
int t=1;
printf("打印各个数字：\n");
do
{
printf("请输出第%d个数:",t);
printf("%d\n",p->data);
p=p->next;
t++;
}while(p);
}
linklist mergelist(void)//两个链表合并
{
int e,n;
linklist pa,pb,pc,head;
printf("请输入第一个链表的长度：");
scanf("%d",&e);
pa=creatlist(e);
printf("请输入第二个链表的长度：");
scanf("%d",&n);
pb=creatlist(n);
head=pc=(linklist)malloc(sizeof(lnode));
pc->next=NULL;
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
return head;
}
void main()
{
linklist head;
head=mergelist();
print(head);
}
///
请输入第一个链表的长度：5
请输入链表中的一个数字：3
请输入第2个数字2
请输入第3个数字1
请输入第4个数字7
请输入第5个数字9
请输入第二个链表的长度：5
请输入链表中的一个数字：6
请输入第2个数字4
请输入第3个数字5
请输入第4个数字8
请输入第5个数字7
打印各个数字：
请输出第1个数:3
请输出第2个数:2
请输出第3个数:1
请输出第4个数:6
请输出第5个数:4
请输出第6个数:5
请输出第7个数:7
请输出第8个数:8
请输出第9个数:7
请输出第10个数:9
Press any key to continue
//程序二、引用yangsen600。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct Node
{
int num;
Node * next;
};
Node * createTail()
{
int x;
Node *head = NULL, *p = NULL, *tail = NULL;
puts("\nplease enter some digits(end of '.'):");
while( 1 == scanf("%d",&x) )
{
p = (Node *)malloc(sizeof(Node));
p->num = x;
p->next = NULL;
if( NULL == head )
{
tail = p;
head = tail;
}
else
{
tail->next = p;
tail = p;
}
}
getchar();
return head;
}
Node * CombinationNode(Node* head1, Node* head2)
{
Node *head,*tail,*p = head1,*q = head2,*s;
if( NULL == p )
return q;
if( NULL == q )
return p;
tail = p;
if( p->num > q->num)
tail = q;
head = tail;
while( NULL != p && NULL != q )
{
if(p->num <= q->num )
//如果p所指元素<q所指元素，那么把p所指元素，率先拉入合并后的链表中，
//p赋给s，并从p的下一个元素p->next查找。
//直到发现p所指 不再 < q，而是p > q了 即转至下述代码的else部分。
{
s = p;
p = p->next;
}
else
{
s = q;
q = q->next;
}
tail->next = s;
tail = s;
}
if( NULL == p )
p = q;
s = p;
tail->next = s;
return head;
}
void printHead(Node *head)
{
if( NULL == head )
return;
printf("List: ");
while(head)
{
printf("%d->",head->num);
head = head->next;
}
puts("NUL");
}
void main( void )
{
Node* head1,*head2,*head;
head1 = createTail();
printHead(head1);
head2 = createTail();
printHead(head2);
head = CombinationNode(head1,head2);
printHead(head);
}
//
please enter some digits(end of '.'):
3 2 1 7 9.
List: 3->2->1->7->9->NUL
please enter some digits(end of '.'):
6 4 5 8 7.
List: 6->4->5->8->7->NUL
List: 3->2->1->6->4->5->7->8->7->9->NUL
Press any key to continue
//与上述那段，输出结果一致。
42题的形式变化：
已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。
//程序三、非递归实现 链表合并排序：
Node * Merge(Node *head1 , Node *head2)
{
if ( head1 == NULL)
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
Node *p1 = NULL;
Node *p2 = NULL;
if ( head1->data < head2->data )
{
head = head1 ;
p1 = head1->next;
p2 = head2 ;
}
else
{
head = head2 ;
p2 = head2->next ;
p1 = head1 ;
}
Node *pcurrent = head ;
while ( p1 != NULL && p2 != NULL)
{
if ( p1->data <= p2->data )
{
pcurrent->next = p1 ;
pcurrent = p1 ;
p1 = p1->next ;
}
else
{
pcurrent->next = p2 ;
pcurrent = p2 ;
p2 = p2->next ;
}
}
if ( p1 != NULL )
pcurrent->next = p1 ;
if ( p2 != NULL )
pcurrent->next = p2 ;
return head ;
}
//程序四、递归实现，
Node * MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->data < head2->data )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}
--------------------------------------------------------------------------------------------------
ok，最后，咱们来透彻比较下上述几段代码的相同与不同。
不放比较一下，程序一、和程序二关于链表合并的核心代码，的区别：
Node * CombinationNode(Node* head1, Node* head2) //程序二
{
Node *head,*tail,*p = head1,*q = head2,*s;
if( NULL == p )
return q;
if( NULL == q )
return p;
tail = p;
if( p->num > q->num)
tail = q;
head = tail;
while( NULL != p && NULL != q )
{
if(p->num <= q->num )
{
s = p; //3.4
p = p->next; //
}
else
{
s = q;
q = q->next;
}
tail->next = s;
tail = s;
}
if( NULL == p )
p = q;
s = p;
tail->next = s;
return head;
}
和这段：
linklist mergelist(void) //程序一
{
int e,n;
linklist pa,pb,pc,head;
printf("请输入第一个链表的长度：");
scanf("%d",&e);
pa=creatlist(e);
printf("请输入第二个链表的长度：");
scanf("%d",&n);
pb=creatlist(n);
head=pc=(linklist)malloc(sizeof(lnode)); //1.这
pc->next=NULL; //2.这
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa; //3.这
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb; //4.这
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
return head;
}
再比较下，程序一与程序四俩段的形式区别：
linklist mergelist(void)//程序一
{
int e,n;
linklist pa,pb,pc,head;
printf("请输入第一个链表的长度：");
scanf("%d",&e);
pa=creatlist(e);
printf("请输入第二个链表的长度：");
scanf("%d",&n);
pb=creatlist(n);
head=pc=(linklist)malloc(sizeof(lnode));
pc->next=NULL;
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa; //3
pc=pa; //1
pa=pa->next; //2
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
return head;
}
和
//递归实现，程序四
Node * MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->data < head2->data )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}
------------------------------
//程序一标明的1、2、3相当于，下述程序四的1、2、3
if ( head1->data < head2->data )
{
head = head1 ; //1.head=head1;
head->next = MergeRecursive(head1->next,head2); //2.head1=head1->next;
//3.head->next=head1
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
聪明的你，相信，不要我过多解释。:)。
作者声明：
本人July对本博客所有任何内容享有版权，转载或引用任何内容、资料，
请注明作者本人 July及出处。谢谢。