Java, 268 ms, two linked lists


  • 0
    F

    I think this is very simple, though it is fast. An even simpler solution is to use 2 array lists (324ms)

    public class Solution
    {
    ListNode small = null;
    ListNode big = null;

    ListNode currS = null;
    ListNode currB = null;
    
    private void addSmall( int val )
    {
    	if ( currS == null )
    	{
    		small = new ListNode( val );
    		currS = small;
    	}
    	else
    	{
    		ListNode newNode = new ListNode( val );
    		currS.next = newNode;
    		currS = newNode;
    	}
    }
    
    private void addBig( int val )
    {
    	if ( currB == null )
    	{
    		big = new ListNode( val );
    		currB = big;
    	}
    	else
    	{
    		ListNode newNode = new ListNode( val );
    		currB.next = newNode;
    		currB = newNode;
    	}
    }
    
    public ListNode partition( ListNode head, int x ) 
    {
    	if ( head == null )
    		return null;
    	
        small = null; big = null;
        currS = null; currB = null;
        
        ListNode curr = head;
        while ( curr != null )
        {
        	if ( curr.val < x )
        		addSmall( curr.val );
        	else
        		addBig( curr.val );
        	curr = curr.next;
        }
        
        if ( small == null )
        	return big;
        else
        {
        	if ( big == null )
        		return small;
        	// concatenate the 2 lists 
        	currS.next = big;
        	return small;
        }
    }
    

    }


Log in to reply
 

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