【第三轮】6.23-6.29 CareerCup 2.4

【解题思路】Use 2 dummy nodes to partition and then link 2 parts together.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/8a0cf0419e646bfd1f7b

【解题思路】traverse the list, if see a node with val <= partition, then move it to the front of the list
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/b2bf5bd3ea3ee7a0e72f

【解题思路】
1. partition in place, use two iterators, one indicating boundary, one traversing the list as runner. if runner is smaller than x, insert it after bound, update bound, and remove it from original position.
2. use two temporary lists, holding smaller and larger parts respectively.
【时间复杂度】
O(N)
【空间复杂度】
1. O(1)
2. O(N)
【gist link】
https://gist.github.com/c569c1fdd39c0e91ad2e

【解题思路】指针操作，分情况swap
【时间复杂度】O(n)
【空间复杂度】O(1)
https://gist.github.com/xun-gong/c851e00b91490b77e170

【解题思路】
使用一个双向列表，遍历链表，碰到比X小的，放到最前面去。
改进：
改成单向链表。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/guchang/bff95e95ad201b335ed5

【解题思路】
traverse the list, put smaller element into beforeList,
put larger element into afterList, and at last append
afterList to beforeList
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/JoshuaTang/bdd2f058c2f3ad04d80a

//【解题思路】
//建立两个链表，一个连接小于x的结点，另一个连接大于等于x的结点，最后合并
//两个链表
//【时间复杂度】
//O(n)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350

【解题思路】
traverse the list and link the node to two differenet lists, one for nodes less than pivot, one for nodes greater than or equal to pivot
link the two list into one list

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/8fbc805dd95161b4e219

Solution3
Idea: modify beyond the original linkedList, just like the partition method in qSort algorithm

Notice: is the implementation below, we just swap the val of the two node, if required to swap the two node:
swap two nodes (node1->next and node2->next) in a linked list,
– first, swap(node1->next, node2->next),
– then, swap(node1->next->next, node2->next->next).

Time Complexity: O(n)
Space Complexity: O(1)

Solution4
Idea: modify beyond the original LinkedList, iterate the list, when the val of the current node is less than x, than move this node to the front of the list

Time Complexity: O(n)
Space Complexity: O(1)

Code:
http://www.jyuan92.com/post-449