算法面试普及后，传统的数据结构和算法课程讲的太过于基础，又远离求职需求。需要发掘更多的前沿的数据结构和算法题展现给读者，以期跟的上时代的步伐。面试官在有限的面试中，让面试者编程解决某些数据结构和算法的问题，通过观察面试者编码的熟练程度、思考的速度和深度来衡量面试者的能力和潜力。相信仔细的推敲逐一攻克后一定会收获颇丰。

下面看题：

1. 给定两个有序 链表 的头指针head1和head2，打印两个链表的公共部分。

   难度：一星

   解：因为是有序链表，所以从两个链表的头开始进行如下判断：

   如果head1的值小于head2，则head1往下移动。

   如果head2的值小于head1，则head2往下移动。

   如果head1的值与head2的值相等，则打印这个值，然后head1和head2都往下移动。

   head1或head2有任何一个移动到null，整个过程停止。

   具体实现请看如下代码：

   

2.反转单向和 双向链表

分别实现反转单向链表和反转双向链表的函数

要求：如果链表长度为N， 时间复杂度 要求为O（N），额外空间复杂度要求为O（1）.

难度：一星

解：

反转单向链表的函数如下，函数反回反转之后链表新的头节点：

反转双向链表的函数如下，函数返回反转之后链表新的头节点：

3.反转部分单向链表

给定一个单向链表的头节点head，以及两个整数from和to，在单向链表上把第from个节点到第to个节点这一部分进行反转。

难度：一星

解：

1. 先判断是否满足1<=from<=to<=N,如果不满足，则直接返回原来的头节点。

2. 找到第from-1个节点fPre和第to+1个节点tPos。fPre即是要反转部分的前一个节点，tPos是反转部分的后一个节点。把反转的部分先反转，然后正确地连接fPre和tPos。

   例如：1->2->3->4->null,假设fPre为节点1，tPos为节点4，要反转部分为2->3. 先反转成3->2，然后fPre连向节点3，节点2连向tPos，就变成了1->3->2->4->null。

3. 如果fPre为null，说明反转部分是包含头节点的，则返回新的头节点，也就是没反转之前反转部分的最后一个节点，也是反转之后反转部分的第一个节点；如果fPre不为null，则返回旧的头节点。

   请参照如下代码reversePart方法：

今天的链表问题就学到这，仔细揣摩，得到成就感不是其他能比的。

未完待续……