分隔鏈表

題目描述：給你一個鏈表的頭節(jié)點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有 小于 x 的節(jié)點都出現(xiàn)在 大于或等于 x 的節(jié)點之前。

你應當 保留 兩個分區(qū)中每個節(jié)點的初始相對位置。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/partition-list/ ??

著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解法一：鏈表遍歷

聲明2個鏈表lessThan和moreThan分別存放小于x的節(jié)點和不小于x的節(jié)點，然后2個指針curLess和curMore分別指向lessThan和moreThan的頭節(jié)點，然后遍歷鏈表head：

• 如果當前節(jié)點小于x，則將當前節(jié)點添加到lessThan鏈表中；

• 如果當前節(jié)點不小于x，則將當前節(jié)點添加到moreThan鏈表中。

鏈表head遍歷完成后，將lessThan和moreThan的尾結點都指向null，避免出現(xiàn)多余的節(jié)點，然后將lessThan的尾結點指向moreThan的頭結點（即將小于x的節(jié)點挪到不小于x的節(jié)點的前面），最后返回lessThan的next節(jié)點即為最后結果。

【每日寄語】 這一生，坎坷太多了，困難也太多了，但人的潛能是無限的，永遠不要在困難的時候想這就是自己最困難的時候，只要你咬緊牙根堅持，你的夢想就會成真。