Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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 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.