Created
May 30, 2015 22:42
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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