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