86题 partition问题

Question

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操作使得相对顺序不发生改变呢？

Answer 1

liuyubobobo 2018-08-04 22:00:38

快排中的partition本身就是会修改元素顺序，这是快排的partition可以原地操作的关键，也是快排是不稳定的核心原因。如果想让快排的partition不修改顺序，只能开辟额外的内存空间。

使用两个新的链表头去操作完全没有改变题目初衷。如果你的操作正确的话，你不需要开辟任何新空间（不需要new），所有任务都是基于原链表的节点操作的（只是指针）。这就叫在原链表上操作。

partition是快排的一个子过程的名字，但是这个单词没有被快排独占。partition本身就是分割的意思。不代表文字里出现partition就是特指快排的这个子过程：）

• 提问者 慕雪9091725 #1

  非常感谢！

• 提问者 慕雪9091725 #2

  谢谢bobo老师，我对partition这个单词理解错了~
  我在想，对链表操作的题目，如果题目要求只能在源链表上操作，其实oj可以把链表的value设为const,然后对比一下进函数前和进函数后每个节点的内存地址是否相同：）

• liuyubobobo 回复 提问者 慕雪9091725 #3

  赞！不过大多数OJ不会做的这么复杂，只是简单地对结果输出作比对：(

点开查看后面1条评论