算法：96.链表划分

https://www.lintcode.com/problem/partition-list/description

描述

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。

你应该保留两部分内链表节点原有的相对顺序。

样例

给定链表1->4->3->2->5->2->null，并且 x=3

返回1->2->2->4->3->5->null

思路

使用两个链表保存节点值小于x和节点值不小于x的节点，遍历整个链表，根据节点值与 x 的比较结果将节点加入两个不同的链表。在遍历完成后再将两个链表连接起来。

代码

上面的实现中，while 循环内部的条件判断比较繁琐，可以想办法改进一下。对于传入参数 head 的参数，因为while的条件中有判断，所以对head的检查也可以去掉。

对于while内部条件判断的优化，可以增加两个临时节点，充当前面所说的两个链表的头部，也就是说两个链表的头部一定是非空的，这样就避免了每次循环都要判断一次。代码如下：

这个实现代码就清爽了很多。

小结

这个题目中一个非常重要的细节是在完成后一定要将链表尾部节点的next置为空，否则会造成连接环，在后续遍历链表时极可能造成死循环。

关于注释，注释应当解释实现原理，而不是解释语句。

注释是使用自然语言，可能产生歧义，而代码是不会有歧义的。