compare every element to x, and sort them accordingly, similar to quicksort kinda.
but i failed to understand 2 things:
numbers itself DON'T GO ANYWHERE, they just stay in memory, IT IS ALL ABOUT TWISTING THE ARROWS - POINTERS btw nodes!!!!!!
so i failed to implement this idea: unwind/ detach your first node, but save the next element to keep going through the original list!
this is the drawing:
x = 20
value found - 12.
12 < 20 , so detach it from original list and make it point to the new "less than x " list!
public static node partition(int x, node list){
node smaller = null ;
node larger = null ;
while(list != null){
node saved_list_next = list.next ;
if(list.data < x){
list.next = smaller ;
smaller = list ;
}
else{
list.next = larger ;
larger = list ;
}
list = saved_list_next ;
}
if(smaller == null) return larger ;
node head = smaller ;
while(smaller.next!= null) smaller = smaller.next ;
node middle = new node((short) -1) ;
smaller.next = middle ;
smaller.next.next = larger ;
return head ;
}
