My accepted solution. Need help optimizing!!


  • 0
    R

    Hi Guys,

    Find below my accepted solution. I used only one fake Head node and tried to reorder the elements in place. Works fine but feels like a whole lotta code. Can someone help me optimize this please?

    Thanks

    public class Solution {
    public ListNode partition(ListNode head, int x) {

        if(head == null || head.next == null)
            return head;
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode current = dummyHead;
        ListNode end, tail;
        
        // find the tail of the list
        while(current.next != null)
            current = current.next;
        
        // Tail pointer to append elements with value >= x to the tail of the list
        // End pointer to keep track of the initial tail element
        tail = end = current;
        current = dummyHead;
        
        // traverse till the the initial end of list
        while(current.next != end){
            
            // move elements >= x to the tail
            // else advance pointer
            if(current.next.val >= x){
                ListNode next = current.next;
                current.next = next.next;
                next.next = null;
                tail.next = next;
                tail = tail.next;
            } else {
                current = current.next;
            }
            
        }
        
        // In case the end node has value >= x 
        // and is not the last node then move it to the tail
        if(end.next != null && end.val >= x){
            current.next = end.next;
            end.next = null;
            tail.next = end;
        }
        
        return dummyHead.next;
    }
    

    }


Log in to reply
 

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