给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

思路

  1. 维护两条链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var partition = function (head, x) {
  const [dummyHead1, dummyHead2] = [new ListNode(), new ListNode()]
  let [cur1, cur2, cur] = [dummyHead1, dummyHead2, head]
  while (cur) {
    if (cur.val >= x) {
      cur2.next = cur
      cur2 = cur
    } else {
      cur1.next = cur
      cur1 = cur
    }
    cur = cur.next
  }
  cur1.next = dummyHead2.next
  cur2.next = null
  return dummyHead1.next
}