题目链接

题目描述：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

实例：

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

题解：

  乍一看本题和快速排序的切分过程有些类似，但快速排序一般应用于数组中，而本题的数据结构为单链表，显然在交换元素部分有明显的区别。不过，双指针的思路可以借鉴。接下来让我们用双指针解决此题。
  解决链表题可以使用建立虚拟头结点的技巧，同时要注意处理野指针。

  • 引入双指针before，after分别用于存储小于x和大于等于x两个链表
  • 两链表设置虚拟头结点可以减少条件判断(自行举例)
  • 用head遍历原有链表
  • 当值小于x，将该结点接入before链表中
  • 当值大于等于x，将该结点接入after链表中
  • head为空跳出循环
  • 现在将after链接到before后
  • 要注意处理掉虚拟头结点，也就是before和after在链接和返回是向后移一位即可达到处理虚拟头结点的效果
      注意，要体会这个过程中，我们没有使用任何额外的空间，只是将原有链表结点进行移动。对于after->next = NULL;，很多盆友可能有疑问，单单知晓这一步是处理野指针显然不能满足大家的求知欲。而通常解释这一步是为了避免形成环形链表。不过，这个解释也有一点点抽象，所以，解决这个问题最好的办法就是打断点自己过一遍程序，一切都明白了。
      当然，因为是题解，我会给出一个例子的手绘示意图，可能会让你更直观的理解为什么要消除环形？还是如上文所说，要么亲力亲为，要么理解那句话。。。

示意图
86分隔链表 - 图1

算法

  1. class Solution {
  2. public:
  3.     ListNode* partition(ListNode* head, int x) {
  4.         if(!head || !head->next)
  5.             return head;
  6.         ListNode* before = new ListNode(0);
  7.         ListNode* headBef = before;
  8.         ListNode* after = new ListNode(0);
  9.         ListNode* headAft = after;
  11.         while(head){
  12.             if(head->val < x){
  13.                 before->next = head;
  14.                 before = before->next;
  15.             }
  16.             else{
  17.                 after->next = head;
  18.                 after = after->next;
  19.             }
  20.             head = head->next;
  21.         }
  22.         after->next = NULL;
  23.         before->next = headAft->next;
  24.         headBef = headBef->next;
  25.         return headBef;
  26.     }
  27. };

若还有疑问可以去英文版leetcode的discuss区看大神们的解答！