题目：2.2.3 Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

代码实现

我们可以分两步解决：

1）遍历链表时，将其一分为二：第一次添加结点，即创建分区时，记住两个分区的header（par1和par2）。之后，用par1p和par2p指向分区的尾部，便于每次迭代向两个分区添加结点。

2） 链接两个分区：将分区2链接到分区1的尾部，并将分区2最后一个结点的next赋值为NULL（非常重要，后面会解释！）。

 

野指针引发的血案

指针par1，par2都没有初始化为NULL，而后面的if却用par1或par2是否等于NULL作为初始化par1h和par2h的条件，另外最终partition1和partition2拼接后，未将最后一个结点的改为NULL，这两个初始化问题都将导致意想不到的运行结果（产生了循环链表，打印时造成死循环）。总结：1）变量除非后面立刻赋值，否则一定要初始化；2）处理链表时，尤其是对一个链表动“大手术”时，一定要注意是不是有next值没有改，导致循环链表。

链表的典型处理方法

前面的实现中，因为初始时指针为空，所以第一次使用之前必须初始化，这使代码变得复杂化了。我们可以添加两个dummy header来简化这个问题，与实现链表的insert()和delete()时的技巧相同。Dummy分配在栈上，函数返回时将直接被回收。总结：不仅是实现链表，只要对链表做大改动，特别是要动头结点时，使用dummy header能让代码变得简洁并且不易出错。

附：二级指针实现

二级指针同样非常简洁，而且也不用在栈上分配两个dummy对象，也许速度上能更快一些。