题目描述（中等难度）

86. Partition List - 图1

题目描述的很难理解，其实回想一下快排就很好理解了。就是快排的分区，将链表分成了两部分，一部分的数字全部小于分区点 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 后移
  7. 1 2 3 4 5 2  x = 3
  8.     ^   ^
  9.     i   j
  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.         }
  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;
  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.         }
  19.         head = head.next;
  20.     } 
  21.     max.next = null;  //这步不要忘记，不然链表就出现环了
  22.     //两个链表接起来
  23.     min.next = max_head.next;
  25.     return min_head.next;
  26. }

时间复杂度：O（n）。

空间复杂度：O（1）。

总

做完了 84、85 连续两个 hard 后，终于可以做个链表压压惊了。本质上就是快排的分区，而在当时被抛弃的用两个数组分别保存，最 naive 的方法，用到链表这里却显示出了它的简洁。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情