本文共 3179 字，大约阅读时间需要 10 分钟。

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

我的想法

感觉用归并排序不会太复杂，但是实际写的时候越写越晕。

class Solution {
       public ListNode sortList(ListNode head) {
           ListNode dummy = new ListNode(-1);        ListNode end = head;        while(end.next != null) {
               end = end.next;        }        mergeSort(dummy, head, end, null);        return dummy.next;    }    private void mergeSort(ListNode first, ListNode start, ListNode end, ListNode last) {
           if(start == end) {
               return;        }        ListNode fast = start, low = start;        if(start.next == end) {
               low = start;        } else {
               while(fast != end && fast.next != null) {
                   fast = fast.next.next;                low = low.next;            }        }                mergeSort(first, start, low, low.next);        mergeSort(low, low.next, end, last);        merge(first, start, end, low, last);    }    private void merge(ListNode first, ListNode start, ListNode end, ListNode mid, ListNode last) {
           ListNode head = first;        ListNode left = start, right = mid.next;        while(left != mid.next && right != null && right != end.next) {
           //这样写忽略了这是一个链表            if(left.val < right.val) {
                   head.next = left;                head = head.next;                left = left.next;            } else {
                   head.next = right;                head = head.next;                right = right.next;            }        }        while(left != mid.next) {
               head.next = left;            head = head.next;            left = left.next;        }        while(right != null && right != end.next) {
               head.next = right;            head = head.next;            right = right.next;        }        head.next = last;    }}

解答

jiuzhang solution

class Solution {
       public ListNode sortList(ListNode head) {
           if (head == null || head.next == null) {
               return head;        }                ListNode mid = findMid(head);        ListNode right = sortList(mid.next);        //这里切断，方便之后的拼接        mid.next = null;        ListNode left = sortList(head);        return merge(left, right);    }    private ListNode merge(ListNode left, ListNode right) {
           ListNode dummy = new ListNode(-1);        ListNode head = dummy;        while(left != null && right != null) {
               if(left.val < right.val) {
                   head.next = left;                left = left.next;            } else {
                   head.next = right;                right = right.next;            }            head = head.next;        }        if(left != null) {
               head.next = left;        } else {
               head.next = right;        }        return dummy.next;    }    private ListNode findMid(ListNode head) {
       	//注意这里fast的起点比low要往后，这样保证每个小段（即使是长度为2的）都能拆分成长度为1的段        ListNode fast = head.next, low = head;        while(fast != null && fast.next != null) {
               fast = fast.next.next;            low = low.next;        }        return low;    }}

转载地址：http://nyqvb.baihongyu.com/