Skip to content

Instantly share code, notes, and snippets.

@mogutou1214
Created May 30, 2015 22:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mogutou1214/7e2bf9814af04a5db5f8 to your computer and use it in GitHub Desktop.
Save mogutou1214/7e2bf9814af04a5db5f8 to your computer and use it in GitHub Desktop.
CC2.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.
public class partitionLinkedList {
public static LinkedListNode Solution(LinkedListNode head, int x) {
if (head == null) return null;
LinkedListNode smaller = new LinkedListNode(0); //dummyhead for list called smaller
LinkedListNode smallerPtr = smaller;
LinkedListNode larger = new LinkedListNode(0); //dummyhead for list called larger
LinkedListNode largerPtr = larger;
LinkedListNode result;
while (head != null) {
if (head.val < x) {
smallerPtr.next = new LinkedListNode(head.val);
smallerPtr = smallerPtr.next;
} else {
largerPtr.next = new LinkedListNode(head.val);
largerPtr = largerPtr.next;
}
head = head.next;
}
smallerPtr.next = larger.next;
result = smaller.next;
return result;
}
}
import junit.framework.TestCase;
public class testPartitionLinkedList extends TestCase {
public void test0() {
LinkedListNode empty = null;
assertEquals(partitionLinkedList.Solution(empty, 3), null);
}
public void test1() {
LinkedListNode a = new LinkedListNode(1);
LinkedListNode b = new LinkedListNode(2);
LinkedListNode c = new LinkedListNode(3);
LinkedListNode d = new LinkedListNode(4);
LinkedListNode e = new LinkedListNode(5);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
a.printList();
LinkedListNode result = partitionLinkedList.Solution(a, 6);
System.out.println(" ");
result.printList();
}
public void test2() {
LinkedListNode a = new LinkedListNode(1);
LinkedListNode b = new LinkedListNode(2);
LinkedListNode c = new LinkedListNode(3);
LinkedListNode d = new LinkedListNode(4);
LinkedListNode e = new LinkedListNode(5);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
a.printList();
LinkedListNode result = partitionLinkedList.Solution(a, 0);
System.out.println(" ");
result.printList();
}
public void test3() {
LinkedListNode a = new LinkedListNode(5);
LinkedListNode b = new LinkedListNode(2);
LinkedListNode c = new LinkedListNode(1);
LinkedListNode d = new LinkedListNode(3);
LinkedListNode e = new LinkedListNode(4);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
a.printList();
LinkedListNode result = partitionLinkedList.Solution(a, 4);
System.out.println(" ");
result.printList();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment