链表常常碰到的问题有：
链表反转 链表中是否有环 删除链表中的p节点,在p节点前面插入节点q， 要求O(1)复杂度
2个链表相交 2个链表合并
判断俩个链表是否相交 给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。 为了简化问题，我们假设俩个链表均不带环。
问题扩展： 1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列?
请修改append函数，利用这个函数实现：
两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5 另外只能输出结果，不能修改两个链表的数据。
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
30、微软面试题：Given a head pointer pointing to a linked list ,please write a function that sort the list in increasing order. You are not allowed to use temporary array or memory copy struct { int data; struct S_Node *next; }Node; Node * sort_link_list_increasing_order (Node *pheader):
题一、 给定单链表，检测是否有环。 使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。 如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
题二、 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。 如果head1==head2，那么显然相交，直接返回head1。 否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2， 那么指针p1由head1开始向后移动len1-len2步，指针p2=head2， 下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点， 否则说明两个链表没有交点。
题三、 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。 运用题一，我们可以检查链表中是否有环。
如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next,
p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，
于是运用题二的方法，我们找到它们的第一个交点即为所求。
题四、只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。 办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。
题五、只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。 办法与前者类似，首先分配一个结点q，将q插入在p后， 接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。都可以做到0(1)复杂度
题六、 链表反转 三个指针，遍历一遍(0(n)复杂度)
复杂链表的复制
题目：有一个复杂链表，其结点除了有一个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)，以复制一个复杂链表。
//图，接下来，自会补上。July、11.19. 分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。 要在不到一个小时的时间里解决这种类型的题目， 我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。
找出链表的第一个公共结点。 题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为： struct ListNode { int m_nKey; ListNode* m_pNext; };
分析： 第一个公共节点，也就是2个链表中的节点的m_pNext 指向的同一个节点。 1） 先遍历2个链表，得到各自的长度，和差sub 2） 长链表先遍历sub个节点，然后2个节点一起遍历 3） 第一次同时指向的同一个节点就是这个commonNode
题目：从尾到头输出链表。输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下： struct ListNode { int m_nKey; ListNode* m_pNext; };
思路一： 辅助栈，需要一个栈空间 思路二： 反转链表，然后遍历 思路三： 递归实现，将printf语句放在递归调用后面。果然妙极。。
在O（1）时间内删除链表结点。 题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下： struct ListNode { int m_nKey; ListNode* m_pNext;
};
函数的声明如下： void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
思路： 保存下一个节点的值tmp，删除下一个节点，当前节点=tmp
有双向循环链表结点定义为： struct node { int data; struct node *front,*next; };
有两个双向循环链表A，B，知道其头指针为：pHeadA,pHeadB，请写一函数将两链表中data值相同的结点删除。
链表和数组的区别在哪里？
分析：主要在基本概念上的理解。 但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生， 谁比较仔细，谁获胜的机会就大。