86. 分隔链表

🟠   🔖  链表 双指针  🔗 力扣 LeetCode

题目

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3

Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2

Output: [1,2]

Constraints:

• The number of nodes in the list is in the range [0, 200].
• -100 <= Node.val <= 100
• -200 <= x <= 200

题目大意

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

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

解题思路

这道题最简单的做法是构造双向链表，不过时间复杂度是 O(n^2)。

更优的方法是新构造 2 个链表，一个链表专门存储比 x 小的结点，另一个专门存储比 x 大的结点。在原链表头部开始扫描一边，依次把这两类点归类到 2 个新建链表中，有点入栈的意思。由于是从头开始扫描的原链表，所以原链表中的原有顺序会依旧被保存下来。最后 2 个新链表里面会存储好各自的结果，把这两个链表，比 x 小的链表拼接到 比 x 大的链表的前面，就能得到最后的答案了。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中节点的数量。算法只需遍历一次链表，对每个节点进行常数时间的操作（判断并连接到合适的链表），因此整体时间复杂度为线性。
• 空间复杂度：O(1)，因为该算法只使用了常量级别的额外空间来存储几个指针（beforeHead、before、afterHead 和 after）。没有使用额外的数据结构来存储节点，因此空间复杂度是常数级别的。

代码

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
	let beforeHead = new ListNode(0, null);
	let before = beforeHead;
	let afterHead = new ListNode(0, null);
	let after = afterHead;

	while (head) {
		if (head.val < x) {
			before.next = head;
			before = before.next;
		} else {
			after.next = head;
			after = after.next;
		}
		head = head.next;
	}
	after.next = null;
	before.next = afterHead.next;
	return beforeHead.next;
};

相关题目

题号	标题	题解	标签	难度
2161	根据给定数字划分数组		数组 双指针 模拟