微软面试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及出处。谢谢。
分享到：
相关推荐
该系列包含了11篇文章，总共300多道面试题，主要聚焦于数据结构、算法以及海量数据处理三大主题。这些内容来源于July在其个人博客（http://blog.csdn.net/v_july_v）上发表的文章集合。 #### 二、数据结构 数据...
因此，深入研究和理解微软面试题，如“ms100(微软面试100题）”，对于提升个人面试表现有着不可估量的价值。 #### 2. 二元查找树转排序双向链表问题 此题目是微软面试中一道经典算法题，要求在不创建新节点的前提...
微软面试题集在软件开发领域一直备受关注，特别是对于那些希望进入微软或类似科技公司的软件工程师来说。微软面试题通常涉及数据结构与算法，是考察应聘者编程能力与问题解决技巧的重要手段。本文档所提供的内容涵盖...
数组和链表的区别 在计算机科学中，数组和链表是两种基本的数据结构，它们都广泛应用于软件开发和算法设计中。然而，数组和链表有着根本的区别，这些区别决定了它们在不同的场景下的应用。 数组 数组是一种连续...
面试题22：链表中倒数第k个节点 面试题23：链表中环的入口节点 面试题24：反转链表 面试题25：合并两个排序的链表 面试题26：树的子结构 面试题27：二叉树的镜像 面试题28：对称的二叉树 面试题29：顺时针打印矩阵
微软作为全球知名的科技巨头，其面试题历来备受关注，这些题目不仅体现了微软对技术人才的期望，也成为了求职者提升自身技能的重要参考资料。本压缩包中的“微软试题合集”涵盖了多个领域的技术问题，旨在测试候选人...
### 第42题：修改链表的append操作 **题目描述**：给定一个链表 `1->2->3` 和一个新节点 `2->3->5`，要求将新节点插入到原始链表中，且保持链表的顺序不变。 **解题思路**：可以通过遍历找到合适的插入位置，然后将...
### 面试题二：寻找链表相交的第一个节点 对于两个链表，可能存在相交的情况，即它们共享一部分节点。为了找到相交的第一个节点，可以先计算出两个链表的长度差，然后让较长的链表先移动这个差值，之后两个链表同时...
微软面试题，输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。适合新手入门结构清晰易懂
在准备这些面试题时，除了理解和记忆答案，更重要的是深入理解背后的原理，并能将理论知识应用到实际问题中。例如，面对一个排序问题，不仅要熟练掌握各种排序算法，还要理解它们的时间复杂度和空间复杂度，以便在...
以下是一些基于微软面试100题中的关键知识点的详细解释： 1. **数据结构**： - **数组**：基础的数据结构，用于存储同类型元素的集合，支持随机访问。 - **链表**：非连续存储，通过指针连接节点，插入和删除操作...
第二篇 C/C++面试题 第3章 C/C++程序基础 3.1 基本概念 面试题1：什么是C语言语句 面试题2：变量的声明和定义有什么区别 面试题3：下列字符中，哪些不是C语言关键字 面试题4：下列变量定义中，哪些是合法的 面试题5...
微软面试100题系列是求职者准备微软技术面试的重要参考资料，它涵盖了计算机科学与信息技术领域的各种核心概念和技能，旨在考察候选人的编程能力、算法理解、系统设计以及问题解决能力。这个系列由July编纂，可能...
P4_算法题备考：数组、链表、树.xmind
在面对这些面试题时，理解基本概念、熟练运用算法和数据结构，并能够进行时间、空间复杂度分析是至关重要的。此外，清晰地表述思路、展示问题解决能力以及代码的可读性也是面试官关注的重点。通过系统性的学习和练习...
根据提供的信息，我们可以总结并扩展出一系列与微软面试100题相关的知识点，特别是针对第一个题目：“把二元查找树转变成排序的双向链表”。 ### 知识点1：二元查找树(Binary Search Tree, BST)的概念 **定义：** ...
微软面试100道题系列是一套针对IT行业内应聘微软等知名科技公司的面试题集，它主要包括三个部分：数据结构、算法和海量数据处理。这些内容是程序员面试中非常重要的三个考察方向。 数据结构是计算机存储、组织数据...
微软面试100题系列是一份针对计算机编程领域，尤其是C语言编程的面试准备资源。这份资料涵盖了多种计算机科学和技术的基础知识，旨在帮助求职者在面试中展现出扎实的理论基础和实践经验。以下将针对C语言、编程和...