[LeetCode] 86. Partition List

轉自LeetCode

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.

<Solution>

這題再多看一個例子，given 3->1 and x = 2，則答案會是 1->3

也就是不管 x 在不在 list 裡，比 x 小的都在前面，大於等於 x 的都在後面

且原本的順序要維持住

解題想法如下

• 分兩個 linked list 來存，一個存比 x 小的 node，一個存大於等於 x 的 node

• 最後再將兩者合併

舉例:

7 -> 3 -> 8 -> 4 -> 1 -> 2，x = 4

round 1: 

list   : 3 -> 8 -> 4 -> 1 -> 2

list 1 :

list 2 : 7

round 2: 

list   : 8 -> 4 -> 1 -> 2

list 1 : 3

list 2 : 7

round 3: 

list   : 4 -> 1 -> 2

list 1 : 3

list 2 : 7 -> 8

round 4: 

list   : 1 -> 2

list 1 : 3

list 2 : 7 -> 8 -> 4

round 5: 

list   : 2

list 1 : 3 -> 1

list 2 : 7 -> 8 -> 4

round 6: 

list   :

list 1 : 3 -> 1 -> 2

list 2 : 7 -> 8 -> 4

combine:

3 -> 1 -> 2 -> 7 -> 8 -> 4

code 如下