#86 - Partition List

Medium • View on LeetCode • View on GitHub

Problem Description

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.

Solution

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
  const result = [];
  const stack = [];

  while (head) {
    const target = head.val >= x ? result : stack;
    target.push(head.val);
    head = head.next;
  }

  return [...stack, ...result].reverse().reduce((a, b) => {
    return new ListNode(b, a);
  }, null);
};