Javascript O(n) Solution using an array


  • 0
    J

    I solved this problem using an array holding references to each node.

    1. I start with two arrays: lowerArr to hold all references to nodes whose value is less than x and higherArr to hold all references of the other nodes. Using a while loop we traverse through the linked list to add/push our node references into their corresponding array.
    2. Using the Javascript concat method, we then combine the two arrays lowerArr and higherArr to give us finalArr, the array which now holds the references for all nodes in order.
    3. Finally, using a for loop, we now iterate through finalArr to change the next pointer of the current node to point to the next node of our finalArr. In addition we have to change the pointer of the last node to point to null.
    4. And just return the newHead!
    var partition = function(head, x) {
        let lowerArr = []
        let higherArr = []
        let curr = head
    
        while (curr !== null) {
            if (curr.val < x) {
                lowerArr.push(curr)
            } else {
                higherArr.push(curr)
            }
    
            curr = curr.next
        }
    
        let finalArr = lowerArr.concat(higherArr),
            newHead = finalArr[0] || null, 
            last = finalArr.length - 1
    
        for (let i = 0; i < last + 1; i++) {
            let node = finalArr[i]
            let nextNode = finalArr[i+ 1]
            if (i === last) {
                node.next = null
            } else {
                node.next = nextNode
            }
        }
    
        return newHead
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.