[分类整理II]微软等100题系列V0.1版：链表面试题集锦

微软等100题系列V0.1版整理II：链表面试题集锦

--

July2010年12月14日

=======================

此微软等100题系列V0.1版，关于链表的面试题，占了11道。

链表，在数据结构中，也是一个最基本的重头戏。

请看：

--------------

第7题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。

问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?

第13题：
题目：输入一个单向链表，输出该链表中倒数第k个结点。
链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};

第24题：
链表操作，
（1）.单链表就地逆置，
（2）合并链表

42.请修改append函数，利用这个函数实现：
两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果，不能修改两个链表的数据。

58.从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。
链表结点定义如下：
struct ListNode
{

int m_nKey;
ListNode* m_pNext;
};

分析：这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。

60.在O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。

链表结点的定义如下：
struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，
还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。

62.找出链表的第一个公共结点。
题目：两个单向链表，找出它们的第一个公共结点。

链表的结点定义为：
struct ListNode
{

int m_nKey;

ListNode* m_pNext;

};
分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。

76.复杂链表的复制

题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};

下图是一个含有5个结点的该类型复杂链表。
图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，
指向NULL的指针没有画出。

请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，
对数据结构透彻的理解以及扎实的编程功底。

77.关于链表问题的面试题目如下：
1.给定单链表，检测是否有环。
使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。
如果p2到达链表尾部，说明无环，
否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，
那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，
下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，
否则说明两个链表没有交点。

3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
运用题一，我们可以检查链表中是否有环。
如果有环，那么p1p2重合点p必然在环中。从p点断开环，

方法为：p1=p, p2=p->next, p->next=NULL。
此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，
于是运用题二的方法，我们找到它们的第一个交点即为所求。

4.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，
然后再将要插入的数据记录在p中。

78.链表和数组的区别在哪里？
分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，
谁比较仔细，谁获胜的机会就大。

79.
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
3.请编写能直接实现strstr()函数功能的代码。

//此链表面试题类，完。

欢迎，你对以上任何一题，提出你见解、思路、算法。

谢谢。:D。

======================

1.关于本微软等公司数据结构+算法面试100题系列V0.1版的郑重声明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
2.完整100题，请参见，
[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
3.更多详情，请参见，本人博客：
My Blog：
http://blog.csdn.net/v_JULY_v
4.所有的资源（题目+答案）下载地址：
http://v_july_v.download.csdn.net/
5.本微软等100题系列V0.1版，永久维护（网友，思路回复）地址：
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html

作者声明:
本人July对本博客所有任何内容和资料享有版权，转载请注明作者本人July及出处。
永远，向您的厚道致敬。谢谢。July、二零一零年十二月十四日。