class 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;
  }

}