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)）---------------------------------------------- 微软 怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？