# Partition a linked list arround an element

This is my code to partition a list into two parts according to a value. I.e. nodes smaller than value x should precede nodes larger than the value x.
It seems correct. Any corner cases I am overseeing or corrections are highly appreciated.

public Node partition(Node head, int x){
Node prev = null;
while(current != null){
if(current.data > x || current == head){
prev = current;
current = current.next;
}
else{
Node next = current.next;
if(prev != null) {
prev.next = next;
}
current = next;
}
}
}

-

I just have a point on naming of your function. You named it partition but you're just rearranging the elements and returning the head pointer! If you want to partition, you may want to return pointers to heads of partitions (the head you already return and another pointer to start of bigger than x partition), this way someone using your function doesn't need to iterate over linked-list to find start of next partition, and this pointer can be easily recorded in if statement in your while loop.

-

Your code logic seems to do only what you mentioned i.e. it will put nodes with values less than x first, followed by nodes with values greater than x. But, I have a couple of questions:

1. Don't you want to have a marker node which indicates where nodes with values less than x stop and nodes with values equal to or greater than x start?
2. Don't you want the nodes with values less than x and greater than x to be sorted on both sides of the list?

Some very minor suggestions:

Code like below:

if(head == null) return head;


are prone to typographical errors like below:

if(head = null) return head;


which will cause if to always evaluate to true.

So, suggested way to write such code is:

if(null == head) return head;

-
At least in Java, you can not write if (head = null). To make the reading easier and natural, I would suggest to continue with if (xyz == null) in Java. –  tb- Jan 11 '13 at 10:54
Sorry, but I had to -1 because of the incorrect statement as pointed out by tb-. Yoda conditions are unnecessary in many modern programming languages, including C# and Java. –  codesparkle Feb 8 '13 at 17:32