【第三轮】6.23-6.29 CareerCup 2.4

2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
use a pointer p, we guarantee the nodes in [head, p] must be smaller than x. Scan the whole linked list, if the node is smaller than x, insert it  after p, and update p.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qianhuang/adb2f6c2fd73cdc1ff89

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

【解题思路】创建3个临时的LinkedList lessThan， equal，largerThan，traverse original linkedList，add corresponding elements to 3 LinkedLists respectively.再将equal和largerThan 2个LinkedList append 到lessThan里面，返回 lessThan这个linkedlist
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/4a1c7b1d06af700a0b44

【解题思路】创建2个临时的LinkedList lessThan， equalandlargerThan，然后遍历，同时考虑lessthan为null的情况
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/qiangusc/14942a249a44fb36de0b

【解题思路】
创建2个临时的LinkedList less， notLess，然后遍历，然后合在一起
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/UncleGarden/c5b19fbe945b21a67846

【解题思路】
创建2个临时的LinkedList less， notLess，然后遍历，然后合在一起
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/UncleGarden/c5b19fbe945b21a67846

【解题思路】
two temp list headers less and noless, iterate the list and append the node to the corresponding list.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/c87a88857239e80785c8

【解题思路】
Two linked list:
left - all nodes less than x
right - all nodes larger than x

Three pointers track:
Head of left
Tail of left
Head of right

Then normal partition procedure

【时间复杂度】
O(N)

【空间复杂度】
O(1) if allowed to mutate the original list

【gist link】
https://gist.github.com/chrislukkk/3901005117455405cf09

【解题思路】创建2个临时的LinkedList lessThan， equalandlargerThan，然后遍历
【时间复杂度】
O(N)
【空间复杂度】O(n)
【gist link】https://gist.github.com/hilda8519/ddec0a1e20ac8074e79c

【解题思路】
I have three linkedlist, one for less, one for equal, one for greater, get all value from original linkedlist,
and save it to correspoding linkedlist, lastly connect these three linkedlist.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/habina/719d2ca521e7695311c9