Solution: Simulation
Create two virtual nodes, small and large, and their smallHead and largeHead headers. If the value of the current node is less than X, it is stored in the Small list; otherwise, it is stored in the Large list. Finally, the remaining nodes of the Large list are disconnected and spliced to the tail of the Small list to return the small list
var partition = function(head, x) {
let small = new ListNode(-1)
let smallHead = small
let large = new ListNode(-1)
let largeHead = large
while (head) {
if (head.val < x) {
small.next = head
small = small.next
} else {
large.next = head
large = large.next
}
head = head.next
}
large.next = null
small.next = largeHead.next
return smallHead.next
};
Copy the code