Function partition

linkedLists/partition.js:13–44

(list, val)

 * list is being manipulated.
 */
export function partition(list, val) {
  let node = list,
    smallerHead,
    smallerTail,
    largerHead,
    largerTail;

  smallerHead = smallerTail = largerHead = largerTail = null;
  while (node) {
    let next = node.next;
    node.next = null;
    if (node.val >= val) {
      if (!largerTail) {
        largerHead = largerTail = node;
      } else {
        largerTail = largerTail.next = node;
      }
    } else if (node.val < val) {
      if (!smallerHead) {
        smallerHead = smallerTail = node;
      } else {
        smallerTail = smallerTail.next = node;
      }
    }
    node = next;
  }

  if (smallerTail) {
    smallerTail.next = largerHead;
  }
  return smallerHead || largerHead;
}