Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x .

Approach:

We iterate through the linked list ,inserting elements into our before list or our after list.Once we reach the end of the linked list and have completed this splitting we merge the two lists.

Solution:

public LinkedListNode partition(LinkedListNode node ,int x)
{
  LinkedListNode beforeStart = null;
  LinkedListNode beforeEnd = null;
  LinkedListNode afterStart = null;
  LinkedListNode afterEnd = null;

 while(node!=null)
 {
   LinkedListNode next =node.next;
   node.next = null;
   if(node.data < x)
   {
      if(beforeStart == null)
      {
         beforeStart =node;
         beforeEnd=beforeStart;
       }
       else
      {
        beforeEnd.next =node;
        beforeEnd=node;
      }
   }
   else
   {
      if(afterStart == null)
       {
          afterStart =node;
           afterEnd =afterStart;
        }
        else
         { 
             afterEnd.next =node;
             afterEnd=node;
         }
   }
  node =next;
 }

  if(beforeStart == null)
      return afterStart;

beforeEnd.next =afterStart;
return beforeStart;

}