Java one pass without two arrays


  • 0
    L

    Most answers here are using the same idea, two arrays.
    I provide an alternative way to solve the problem. The idea of my solution is move the node in place, I admit that this would be more complex than using two arrays. Anyway, just an alternative.

    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
    
        ListNode pre = null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
    
        // move to the first node that need to be inserted after
        // e.g. [dummy] 1 2 3 4 5  (x: 3) -> dummy 1 [2] 3 4 5
        while (cur.next != null && cur.next.val < x) {
            pre = cur;
            cur = cur.next;
        }
        
        // mark the position
        ListNode index = cur;
        
        // traverse the rest
        pre = cur;
        cur = cur.next;
        
        while (cur != null) {
            if (cur.val < x) {
                // drop the node from original position
                pre.next = cur.next;
                
                // insert it in the index position
                cur.next = index.next;
                index.next = cur;
                index = index.next;
                cur = pre.next;
            } else {
                // step next
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }

Log in to reply
 

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