Partition Linked list around 'x'

Write code to partition a linked list around a value x, such that all nodes less than x come before alt nodes greater than or equal to x.

by Vikram Deshmukh

JavaScript

function Node(value, nxt) {
	this.data = value;
	this.next = nxt;
}
const root1 = new Node(3, new Node(4, new Node(7, new Node(3, new Node(9, new Node(5, new Node(8, new Node(2, null)))))))); 

function printLL(root) {
	let temp = root;
	let str = '';
	while(temp) {
		str += temp.data +" > ";
		temp = temp.next;
	}
	console.log(str+" null");
}
function partition(root, x) {

	if(!root || !root.next) return root;
	let left = null;
	let leftRoot = null;
	let right = null;
	let rightRoot = null;
	let cursor = root;
	while(cursor) {
		if(cursor.data < x) {
			if(left != null) {
				left.next = cursor;
			} else {
				leftRoot = cursor;
			}
			left = cursor;
		} else {
			if(right != null) {
				right.next = cursor;
			} else {
				rightRoot = cursor;
			}
			right = cursor;
		}
		cursor = cursor.next;
	}
	
	// 
	// 
	// 
	// 
	if(!left && !right) {
		// shouldn't come here
		return root;
	} else if (!left && right) {
		right.next = null;
		return rightRoot;
	} else if (left && !right) {
		left.next = null;
		return leftRoot;
	} else { // if(left && right) {
		left.next = rightRoot;
		right.next = null;
		return leftRoot;
	}
	
	throw new Error("Shouldn't be here");
}

printLL(root1);
printLL(partition(root1, 4));
//printLL(partition(null, 6));