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;
}