题目描述（中等难度）

题目描述的很难理解，其实回想一下快排就很好理解了。就是快排的分区，将链表分成了两部分，一部分的数字全部小于分区点 x，另一部分全部大于等于分区点 x。最后就是 1 2 2 和 4 3 5 两部分。

解法一

回顾下快排的解法，快排中我们分区用了两个指针，一个指针表示该指针前边的数都小于分区点。另一个指针遍历数组。 1. 1 4 3 2 5 2 x = 3 2. ^ ^ 3. i j 4. i 表示前边的数都小于分区点 3, j 表示当前遍历正在遍历的点 5. 如果 j 当前指向的数小于分区点，就和 i 指向的点交换位置，i 后移 6. 7. 1 2 3 4 5 2 x = 3 8. ^ ^ 9. i j 10. 11. 然后继续遍历就可以了。

这道题无非是换成了链表，而且题目要求不能改变数字的相对位置。所以我们肯定不能用交换的策略了，更何况链表交换也比较麻烦，其实我们直接用插入就可以了。 同样的，用一个指针记录当前小于分区点的链表的末尾，用另一个指针遍历链表，每次遇到小于分区点的数，就把它插入到记录的链表末尾，并且更新末尾指针。dummy 哨兵节点，减少边界情况的判断。 1. public ListNode partition(ListNode head, int x) { 2. ListNode dummy = new ListNode(0); 3. dummy.next = head; 4. ListNode tail = null; 5. head = dummy; 6. //找到第一个大于等于分区点的节点，tail 指向它的前边 7. while (head.next != null) { 8. if (head.next.val >= x) { 9. tail = head; 10. head = head.next; 11. break; 12. }else { 13. head = head.next; 14. } 15. } 16. while (head.next != null) { 17. //如果当前节点小于分区点，就把它插入到 tail 的后边 18. if (head.next.val < x) { 19. //拿出要插入的节点 20. ListNode move = head.next; 21. //将要插入的结点移除 22. head.next = move.next; 23. //将 move 插入到 tail 后边 24. move.next = tail.next; 25. tail.next = move; 26. //更新 tail 27. tail = move; 28. }else{ 29. head = head.next; 30. } 31. 32. } 33. return dummy.next; 34. }

时间复杂度：O（n）。 空间复杂度：O（1）。

解法二

官方给出的 solution 也许更好理解一些。 我们知道，快排中之所以用相对不好理解的双指针，就是为了减少空间复杂度，让我们想一下最直接的方法。new 两个数组，一个数组保存小于分区点的数，另一个数组保存大于等于分区点的数，然后把两个数组结合在一起就可以了。 1. 1 4 3 2 5 2 x = 3 2. min = {1 2 2} 3. max = {4 3 5} 4. 接在一起 5. ans = {1 2 2 4 3 5}

数组由于需要多浪费空间，而没有采取这种思路，但是链表就不一样了呀，它并不需要开辟新的空间，而只改变指针就可以了。 1. public ListNode partition(ListNode head, int x) { 2. //小于分区点的链表 3. ListNode min_head = new ListNode(0); 4. ListNode min = min_head; 5. //大于等于分区点的链表 6. ListNode max_head = new ListNode(0); 7. ListNode max = max_head; 8. 9. //遍历整个链表 10. while (head != null) {
11. if (head.val < x) { 12. min.next = head; 13. min = min.next; 14. } else { 15. max.next = head; 16. max = max.next; 17. } 18. 19. head = head.next; 20. } 21. max.next = null; //这步不要忘记，不然链表就出现环了 22. //两个链表接起来 23. min.next = max_head.next; 24. 25. return min_head.next; 26. }

时间复杂度：O（n）。 空间复杂度：O（1）。

总

做完了 84、85 连续两个 hard 后，终于可以做个链表压压惊了。本质上就是快排的分区，而在当时被抛弃的用两个数组分别保存，最 naive 的方法，用到链表这里却显示出了它的简洁。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情