/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
const partition = function (head, x) {
  const leftHead = new ListNode();
  const rightHead = new ListNode();
  let left = leftHead;
  let right = rightHead;

  // split list into two sides, left if val < x, else right
  for (let node = head; node !== null; node = node.next) {
    if (node.val < x) {
      left.next = node;
      left = node;
    } else {
      right.next = node;
      right = node;
    }
  }

  // combine the two sides
  left.next = rightHead.next;
  right.next = null;

  return leftHead.next;
};

// another

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
const partition = function (head, x) {
  const left = [];
  const right = [];
  let containX = false;
  let cur = head;
  while (cur !== null) {
    if (containX === true) {
      if (cur.val < x) {
        left.push(cur);
      } else {
        right.push(cur);
      }
    } else {
      if (cur.val >= x) {
        containX = true;
        right.push(cur);
      } else {
        left.push(cur);
      }
    }
    cur = cur.next;
  }
  const arr = left.concat(right);

  for (let i = 0; i < arr.length; i++) {
    if (i === arr.length - 1) {
      arr[i].next = null;
    } else {
      arr[i].next = arr[i + 1];
    }
  }
  return arr[0] == null ? null : arr[0];
};
