Skip to content

Instantly share code, notes, and snippets.

@chouclee
Created June 23, 2014 06:44
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save chouclee/4a1c7b1d06af700a0b44 to your computer and use it in GitHub Desktop.
[CC150][2.4] Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.
import java.util.LinkedList;
public class partition {
public static<T extends Comparable<? super T>> LinkedList<T> parti(LinkedList<T> list, T pivot) {
LinkedList<T> lessThan = new LinkedList<T>();
LinkedList<T> equal = new LinkedList<T>();
LinkedList<T> largerThan = new LinkedList<T>();
int cmp;
for (T element : list) {
cmp = element.compareTo(pivot);
if (cmp < 0)
lessThan.add(element);
else if (cmp == 0)
equal.add(element);
else largerThan.add(element);
}
lessThan.addAll(equal);
lessThan.addAll(largerThan);
return lessThan;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<Integer> test = new LinkedList<Integer>();
for (int i = 10; i > 0; i--)
test.add(i);
System.out.println(test.toString());
test = partition.parti(test, 5);
System.out.println(test.toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment