给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 先找到最后一个比 x 小的节点，设为 start
- 再用相邻的两个指针从头遍历链表
- 如果右侧的指针比 x 小，移动到下一个
- 则，右侧的指针比 x 大
- 把右侧指针指向的节点连接到尾节点后面
- 尾结点右移一位
当中，因为要判断第二次遍历的终止条件，所以需要一个额外的指针来代替尾结点来进行右移，原尾结点不动。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
if (!head || !head.next) return head
let dum = new ListNode(0, head)
let start = current = head
while (current) {
if (current.val < x) {
start = current
}
current = current.next
}
let tempTail = start
let slow = dum, fast = head
while (fast !== start) {
if (fast.val >= x) {
let temp = fast.next
slow.next = temp
fast.next = tempTail.next
tempTail.next = fast
fast = temp
tempTail = tempTail.next
} else {
slow = fast
fast = fast.next
}
}
return dum.next
};其实先找到「第一个比 x 大的」要比先找到「最后一个比 x 小的」要快，而且终止条件的判断也更简单：链表结尾即为遍历终止。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
if (!head || !head.next) return head
let dum = new ListNode(0, head)
let start = dum
while (start.next && start.next.val < x) {
start = start.next
}
let slow = start, fast = start.next
while (fast) {
if (fast.val < x) {
slow.next = fast.next
fast.next = start.next
start.next = fast
fast = slow.next
start = start.next
} else {
slow = fast
fast = fast.next
}
}
return dum.next
};。。其实没有更快