归并排序

归并排序的时间复杂度为：O()

public ListNode merge(ListNode first, ListNode second) {

        ListNode dummyHead;

        ListNode curr;

        dummyHead = new ListNode(0);

        curr = dummyHead;

        while (first != null && second != null) {

            if (first.val <= second.val) {

                curr.next = first;

                first = first.next;

            } else {

                curr.next = second;

                second = second.next;

            }

            curr = curr.next;

        }

        curr.next = (first == null) ? second : first;

        return dummyHead.next;

    }

    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) {

            return head;

        }

        ListNode middleListNode = getMiddleNode(head);

        ListNode secondHalfHead = middleListNode.next;

        middleListNode.next = null;

        return merge(sortList(head), sortList(secondHalfHead));

    }

    public ListNode getMiddleNode(ListNode head) {

        if (head == null) {

            return head;

        }

        /**

        * 快慢指针

        */

        ListNode fast;

        ListNode slow;

        fast = slow = head;

        while (fast.next != null && fast.next.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }