86题 partition问题
来源：5-2 测试你的链表程序
慕雪9091725
2018-08-04
bobo老师你好，对86题我使用单路快排的思路，把swap操作改为指针操作后，发现答案出错，因为使用单路快排改变了数据的相对顺序，比如对样例的 partition（｛1，4，3，2，5，2｝，3） 原链表经过交换操作依次变为{1,2,3,4,5,2},{1,2,2,4,5,3}.这与预期答案的{1,2,2,4,3,5}不符，改变了3和5的相对顺序，然后我使用用2个新的链表头去分别连接小于和大于等于的键值最后再把2个链表相连的方式解决了这个问题，但我觉得这样改变了题目的初衷，毕竟题目应该意思是在源链表上进行指针操作，而且题目名字也叫partitionList。请问bobo老师我应该如何修改partition操作使得相对顺序不发生改变呢？
写回答
1回答
-
快排中的partition本身就是会修改元素顺序，这是快排的partition可以原地操作的关键，也是快排是不稳定的核心原因。如果想让快排的partition不修改顺序，只能开辟额外的内存空间。
使用两个新的链表头去操作完全没有改变题目初衷。如果你的操作正确的话，你不需要开辟任何新空间（不需要new），所有任务都是基于原链表的节点操作的（只是指针）。这就叫在原链表上操作。
partition是快排的一个子过程的名字，但是这个单词没有被快排独占。partition本身就是分割的意思。不代表文字里出现partition就是特指快排的这个子过程：）
042018-08-04
相似问题