微软面试100题V0.1版第42题合并链表解答
July、网友二零一一年一月2日
<!--EndFragment-->
------------------------------------
本文参考：本人整理的微软面试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及出处。谢谢。
分享到：
相关推荐
面试题总结：数组和链表的区别 数组和链表.pdf
P4_算法题备考：数组、链表、树.xmind
微软面试题，输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。适合新手入门结构清晰易懂
第二篇 C/C++面试题 第3章 C/C++程序基础 3.1 基本概念 面试题1：什么是C语言语句 面试题2：变量的声明和定义有什么区别 面试题3：下列字符中，哪些不是C语言关键字 面试题4：下列变量定义中，哪些是合法的 面试题5...
合并链表，设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。
java基础面试题合并2个排序的链表本资源系百度网盘分享地址
数据结构，链表所有综合面试题型汇总，有大神漏缺的给我留言
面试题 1：二维数组中的查找(考点： 数组) 1 面试题 2：替换空格(考点： 字符串) 2 面试题 3：从尾到头打印链表(考点： 链表) 2 面试题 4：重建二叉树(考点： 树) 4 面试题 5：用两个栈实现队列(考点： 栈和...
8580 合并链表
python数据结构实现（一）：数组和链表及相关LeetCode题 数组和链表.pdf
重点阐述数据结构： 结构体与链表，深入详解数据结构。
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
这是采用链表进行的合并两个有序链表操作，希望对大家的学习有帮助哟！
js代码-面试题9：链表
python python_leetcode面试题解之第23题合并k个升序链表_python题解
输入一个链表的头结点，反转该链表，并返回反转后链表的头结点 这是一道广为流传的微软面试题
C语言链表类面试题.docx struct node { int data; struct node* next; }; 创建单链表的程序为： struct node* create(unsigned int n) { //创建长度为n的单链表 assert(n > 0); node* head; head = new ...
题一、给定单链表，检测是否有环。题二、 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。等面试题。
从键盘输入两个链表，通过程序对他们排序，之后按递增顺序合并链表
数据结构：单向循环链表源码，为了让读者有更好的体验，把源码上传上去，有任何问题，或者有任何bug可以直接私信我，我会及时回复，并且解决对应问题