Java, 268 ms, two linked lists

• 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 )
else
curr = curr.next;
}

if ( small == null )
return big;
else
{
if ( big == null )
return small;
// concatenate the 2 lists
currS.next = big;
return small;
}
}
``````

}

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