Leetcode 86. Partition List - Given 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.

leetcode-86-partition-linked-list.js

const partition = (head, x) => {
  if(head === null) return head;
  let beforeStart = null,
      beforeEnd = null,
      afterStart = null,
      afterEnd = null;
  
  while(head) {
    let next = head.next;
    head.next = null;
    if(head.val < x) {
      if(!beforeStart) {
        beforeStart = head;
        beforeEnd = beforeStart;
      } else {
        beforeEnd.next = head;
        beforeEnd = head;
      }
    } else {
      if(!afterStart) {
        afterStart = head;
        afterEnd = afterStart;
      } else {
        afterEnd.next = head;
        afterEnd = head;
      }
    }
    head = next;
  }
  
  if(!beforeStart) {
    return afterStart;
  }
  
  beforeEnd.next = afterStart;
  return beforeStart;
};