Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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){  
   if(head == null) return head;  
   Node prev = null;  
   Node current = head;  
   while(current != null){  
       if(current.data > x || current == head){  
           prev = current;  
           current = current.next;  
       }  
       else{  
           Node next = current.next;  
           current.next = head;   
           if(prev != null) {
              prev.next = next;   
           }   
           head = current;  
           current = next;  
      }  
   }
   return head;  
}
share|improve this question

2 Answers 2

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.

share|improve this answer

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; 
share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.