PartitionList { public ListNode<Integer> split(ListNode<Integer> list, int x) { validateInput(list); ListNode<Integer> before = null; ListNode<Integer> after = null; while (list != null) { ListNode<Integer> next = list.getNext(); if (list.getData() < x) { list.setNext(before); before = list; } else { list.setNext(after); after = list; } list = next; } if (before == null) { return after; } ListNode<Integer> result = mergeLists(before, after); return result; }  ListNode<Integer> split(ListNode<Integer> list, int x);  }
@Test(expected = IllegalArgumentException.class) public void shouldNotAcceptNullLists() { partitionList.split(null, 1); }
@Test public void shouldNotSplitListIfXIsMinorThanEveryNode() { ListNode<Integer> list = createList(new int[] { 1, 2, 3 }); ListNode<Integer> result = partitionList.split(list, 0); assertListContainsElements(new Integer[] { 3, 2, 1 }, result); }
@Test public void shouldNotSplitListIfXIsGreaterThanEveryNode() { ListNode<Integer> list = createList(new int[] { 1, 2, 3 }); ListNode<Integer> result = partitionList.split(list, 4); assertListContainsElements(new Integer[] { 3, 2, 1 }, result); }
@Test public void shouldSplitListUsingX() { ListNode<Integer> list = createList(new int[] { 3, 1, 2 }); ListNode<Integer> result = partitionList.split(list, 2); assertListContainsElements(new Integer[] { 1, 2, 3 }, result); }