【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;

代碼：