【第三轮】6.23-6.29 CareerCup 2.4

【解题思路】
set 2 list, one of nodes less than x and another of nodes more or equal to x;
insert into the lists from their head
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/f0c185fa59129c3f74d4

【解题思路】
Go through the list, if we see a node whose value is smaller than x,
         * delete it and then insert it to the head of the list
【时间复杂度】
O(n)
【空间复杂度】
O(1) if we are allowed to mutate the original list
【gist link】
https://gist.github.com/XiaoxiaoLi/80318ea564c6ad527c8e

【解题思路】create two list, scan over the original list and store all less elements in one list and all greater elements in another list. combine the two list
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/pchong90/f91f6e2c522f28cacbd4

【解题思路】Traverse the list, separate the list into two part with the original nodes, then return them with a node array.
【时间复杂度】O(n)
【空间复杂度】O(1) use 3 extra Node to save the middle node, larger head, less header
【gist link】https://gist.github.com/bitcpf/f51b82718f54bddfae74

【解题思路】create two list for less than x and not less x, traverse the list
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/yokiy/e60fc4079f4b7f9d3443

【解题思路】
Try to make it done without using external space, then need to keep track of head,tail and current processing node.
1. suppose that do not know the tail, then need to traverse it one time
2. traverse the list , if a node is less than x, move it to the head, otherwise, move it to the tail
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】

补充内容 (2014-6-30 08:32):
https://github.com/FinalF/CarrerUp/blob/master/moveAroundX.java

【解题思路】If we are allowed to modify the original linkedlist, we can traverse the whole list and keep the larger nodes unchanged, move the smaller nodes to the front of the linkedlist.   If not,  create two extra linkedlists for smaller nodes and larger nodes and then combine them.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jyhjuzi/ecaa9bf88b5858fe1f13

【解题思路】Use two linked lists, less and greater, if a node is smaller than val, append it to less, if it's larger than val, append it to greater. Then append greater to less.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/c63425af7a01dee9e868

【解题思路】
Ues two linked list: Less and NotLess.
Then iterate the original list and add the nodes to the corresponding list
Return the Less.addAll(NotLess)
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/weazord/ccfc5431a6748e968bd2