SortLinkedList.java

package linkedlists;

public class SortLinkedList {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            this.val = x;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode curr = this;
            while (curr != null) {
                sb.append(curr.val);
                sb.append(" ");
                curr = curr.next;
            }
            return sb.toString();
        }
    }

    static class Pair {
        public ListNode first;
        public ListNode second;

        Pair(ListNode first, ListNode second) {
            this.first = first;
            this.second = second;
        }
    }

    static Pair findMidAndDetach(ListNode begin) {
        // No nodes.
        if (begin == null) {
            throw new IllegalStateException("List can not be null.");
        }
        // One node.
        else if (begin.next == null) {
            throw new IllegalStateException("List can not have one node.");
        }
        // Two nodes.
        else if (begin.next.next == null) {
            ListNode second = begin.next;
            begin.next = null;
            return new Pair(begin, second);
        }
        // Everything else.
        else {
            ListNode fast = begin;
            ListNode slow = begin;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode second = slow.next;
            slow.next = null;
            return new Pair(begin, second);
        }
    }

    static ListNode merge(ListNode first, ListNode second) {
        ListNode current = new ListNode(-1);
        ListNode dummyResult = new ListNode(-1);
        dummyResult.next = current;
        while (first != null && second != null) {
            if (first.val <= second.val) {
                current.next = first;
                first = first.next;
            } else {
                current.next = second;
                second = second.next;
            }
            current = current.next;
        }

        while (first != null) {
            current.next = first;
            first = first.next;
            current = current.next;
        }

        while (second != null) {
            current.next = second;
            second = second.next;
            current = current.next;
        }

        return dummyResult.next.next;
    }

    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        } else {
            Pair pairOfNodes = findMidAndDetach(head);
            return merge(sortList(pairOfNodes.first), sortList(pairOfNodes.second));
        }
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(4);
        ListNode n2 = new ListNode(3);
        ListNode n3 = new ListNode(1);

        n1.next = n2;
        n2.next = n3;
        System.out.println(sortList(n1));

    }
}