【leetcode】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 <code>1-&gt;4-&gt;3-&gt;2-&gt;5-&gt;2</code> and x =

3,

return <code>1-&gt;2-&gt;2-&gt;4-&gt;3-&gt;5</code>.

不是很麻烦的一道题，首先找到链表中第一个比x大或者等于x的数，它的指针存放在before_p中，那么后面比x小的数都插入到它前面就可以了。在遍历的过程中，还要用指针front_p保存p的前一个指针，方便删除p所指向的节点。开始时候没有用这个指针，后来发现当删除的元素在链表结尾的时候，这个指针是必须的。

一种特殊的情况是需要头插的时候，比如

1. 给定的序列是2-&gt;1，给定的x是2，此时1要被头插到2前面去；

2. 给定的序列是2-&gt;3-&gt;1，x是3的时候1只需插入到2的后面，要注意这两种情况的区别。

利用判断before_p == head &amp;&amp; before_p-&gt;val &gt;=

x，就可以甄别出要头插的情况了。因为在before_p ==

head时，有两种情况，一种是before_p指向的元素确实比x大或者相等，对应上述的第一种情况，需要头插；另外一种before_p指向的元素比x小，只需要把元素插入到before_p后面就可以了，对应于上述的第二种情况。

WA了一次才发现的，一般好难想到这一点&gt;.&lt;

代码：