86. Partition List

🟠   🔖  链表 双指针  🔗 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

题目大意

给定一个数 x，大于或等于 x 的数字都要排列在比 x 小的数字后面，并且相对位置不能发生变化。由于相对位置不能发生变化，所以不能用类似冒泡排序的思想。

解题思路

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

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

代码

/**
 * @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. 根据给定数字划分数组

- [2161. 根据给定数字划分数组](https://leetcode.com/problems/partition-array-according-to-given-pivot)