[第二轮] 2/25-3/3 CareerCup 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 of equal to x.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

grassgigi 发表于 2013-2-26 13:50
我打错了.那个方法是partition，不是pivot，应该就在算法导论quicksort刚开始的地方。。

我的代码有点 ...

那如果LinkedList里面有两个数和当前函数给的参数一样怎么处理呢？

我已开始也想到的是用QuickSort里面的partition，但是发现好像碰到参数和value一样的情况就会有问题

通解是SORT

use 2 list to hold first part and second part, then merge them
https://gist.github.com/mazl123321/5024847

Use two pointers to iterate the list, one(pointer i) from head to tail, the other one (pointer j) from tail to top. When the element pointed by i is not less than X and the element pointed by j is less than X, exchange the element of these two nodes. Go on until i and j meet.

Just like the partition of Quicksort.

一前一后两个指针遍历链表，将小于Value值的节点插入新的链表，最后将新链表接在原表之前。
run time O(N), space O(1)
https://gist.github.com/Zuohr/5029117

https://gist.github.com/mettaworld/5035779
Java language

直接参照CLRS上quick sort的pivot方法
https://gist.github.com/chrislukkk/5036670

请问面试的时候如果要交换list中的两个node，可以默认交换的是node里的value吗？还是应该交换node本身呢？
感觉交换node本身的话比较麻烦，还要多加指针去track previous node。

grassgigi 发表于 2013-2-26 14:21
直接参照CLRS上quick sort的pivot方法
https://gist.github.com/chrislukkk/5036670

好酷的样子！我用Java试了下你的算法，好像遇到了点问题，比如链表是7-6-5-4-3-2，如果X为4，那么第一次交换后就变成3-6-5-4-7-2，第二次交换 3-2-5-4-7-6，然后n就走到底了，可是还剩了个5在4前面呢，不知道是不是哪里理解错了。。。另外请问这个quicksort的pivot方法在哪个章节啊。
交换Node确实很坑爹啊。。。

zuohr 发表于 2013-2-26 20:43
好酷的样子！我用Java试了下你的算法，好像遇到了点问题，比如链表是7-6-5-4-3-2，如果X为4，那么第一次交 ...

我打错了.那个方法是partition，不是pivot，应该就在算法导论quicksort刚开始的地方。。

我的代码有点问题 我改了下 谢谢~
考虑了两种情况

第一种 x equals to some node value in list
比如3-6-5-4-7-2， x = 4
这种情况下我先把4交换到链表最后， 变成：3-6-5-2-7-4，
然后再进行partition，最后得到3-2-4-6-7-5如果不把4移到最后的话就会出现你回复里那样的问题变成3-2-5-4-7-6

第二种就是x does not equal any node value in list
这种情况x不存在于list中，那么直接调用partition就可以了
比如1-6-5-4-7-2， x= 3 最后得到1-2-5-4-7-6

不知道还有什么没考虑到吗..

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