Skip to main content

分隔链表

题目​

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

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

提示:
  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
示例

86-partition

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

输出: [1, 2, 2, 4, 3, 5]

题解​

麻了, 一开始还妄图使用双指针. 其实思路很简单, 新建两个链表, 一个用于存储原链表小于 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) {
  let small = new ListNode(0)
  const smallHead = small

  let large = new ListNode(0)
  const largeHead = large

  while (head) {
    if (head.val < x) {
      small.next = head
      small = small.next
    } else {
      large.next = head
      large = large.next
    }

    head = head.next
  }

  large.next = null
  small.next = largeHead.next

  return smallHead.next
}