微软等公司数据结构+算法面试100题--链表

1.（原第7题）
----------------------------------------------
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?


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


3.（原第24题）
----------------------------------------------
链表操作
（1）单链表就地反向
（2）合并排好序的链表


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


5.（原第58题）
----------------------------------------------
从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};


6.（原第60题）
----------------------------------------------
在 O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在 O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);


7.（原第62题）
----------------------------------------------
找出链表的第一个公共结点。
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。


8.（原第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)，以复制一个复杂链表。
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，
对数据结构透彻的理解以及扎实的编程功底。


9.（原第77题）
----------------------------------------------
关于链表问题的面试题目如下：
1.给定单链表，检测是否有环。
2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
4.只给定单链表中某个结点 p(并非最后一个结点，即 p->next!=NULL)指针，删除该结点。
5.只给定单链表中某个结点 p(非空结点)，在 p 前面插入一个结点。


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


11.（原第79题(1)）
----------------------------------------------
编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？


12.（原第89题(1)）
----------------------------------------------
2005年11月15日华为软件研发笔试题。实现一单链表的逆转。


13.（原第90题(3)）
----------------------------------------------
判断单链表中是否存在环。


14.（原第97题(2)）
----------------------------------------------
微软
在链表里如何发现循环链接？


15.（原第98题(6)）
----------------------------------------------
微软
怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？