1
\$\begingroup\$

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;  
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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