分隔链表（86）

题目

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

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

示例

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

算法

使用sentinel作为大于等于x的所有节点组成的链表的哨兵节点，使用sentinelSmall作为小于x的所有节点组成的链表的哨兵节点

我们将sentinel.next指向head，然后遍历整个链表，将小于x的节点从链表中取出并让sentinelSmall.next指向它，当遍历完整个链表时，我们将sentinelSmall（此时指向了小于x的节点组成的链表的末尾节点）的next指向sentinel.next（即大于等于x的节点组成的链表的头部）

最后我们返回小于x的链表的头节点即可

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

const partition = (head, k) => {
	let sentinel = new ListNode();
	sentinel.next = head;
	let node = sentinel;
	let smallHead = new ListNode();
	let sentinelSmall = smallHead;
	while (node.next) {
		if (node.next.val < x) {
			smallHead.next = node.next;
			node.next = node.next.next;
			smallHead = smallHead.next;
		} else {
			node = node.next;
		}
	}
	smallHead.next = sentinel.next;
	return sentinelSmall.next;
};