[第二轮] 2/25-3/3 CareerCup 2.4

qsort思想，2个指针，第二个指针一直扫，小于等于pivot跟第一个指针swap.
https://gist.github.com/skxie/d0a11009756fe37d4720

https://github.com/quantumrose/C ... /2.4.Partition.java
create two linked lists to hold node less than x and nodes greater than or equal to x, then merge

https://gist.github.com/lazyGoose/5053421

create two LinkNode l1, l2,  iterate the head, put the smaller element into l1 and larger ones into l2. Then, merge l1 and l2, return l1 + l2

Solution: Use the idea of qsort, two pointers, to traverse the list:
1. start location for the first pointer: the first pointer stops once a value if found to be greater than x;
2. start location for the second pointer: starts from the node right after the first pointer
3. then the second pointer starts to traverse the rest node. if value less than x is found, then swap the two nodes' value information and move the first pointer to the next.
Time complexity: O(n); Space complexity: O(1)

c/c++ 实现

https://github.com/StanleyLee/CareerCup/blob/master/2_4.cpp

Use a pointer called middle to divide the list into three parts: (<x) nodes, (=x) nodes and (>x) nodes. For each iteration, move current nodes to the right place. This way I have to handle more edge conditions.
https://github.com/moophis/careercup/blob/master/2.2-4.cpp#L177

Fanyare 发表于 2013-2-28 03:22
https://github.com/quantumrose/CareerCup/blob/master/2.4.Partition.java
create two linked lists to  ...

先用一个指针读出x VALUE,再从头指针遍历，大于等于value X的移至linked list尾巴 就可以吧？

https://github.com/longwei/Algo/ ... /ch2/Partition.java
stable partition.
用qsort的办法很巧， 等下试一下

https://gist.github.com/ThunderXu/5069631
iterate the list and remove elements to a new list if it < x, at last link this two lists.

https://gist.github.com/flatlight/5069987
use two linked list to hold the nodes in two partitions, then concatenate these two

* Method: Get the smaller elements and hold them in a linked list,
* link the original list after the new list.
C language:
https://gist.github.com/hukun01/5074100