leetCode解题报告之Sort List-蒲公英云

勉励自己：坚持，谁说做工程的人不能学好算法！为面试做准备,加油！！！！！

题目：

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

分析：

题目要求我们要用一个复杂度O(nlogn)的排序算法来排序一个链表，复杂度O(nlogn)的排序算法包括：快速排序，堆排序，希尔排序，二叉排序树排序，归并排序

情况：

考虑到题目的要求，我个人觉得用“归并排序”会比较好！

第一次提交没AC的Time Limit Exceeded代码：(没有考虑到两个递归之后的子链表做排序的话，关于合并的时间消耗)

package cn.xym.leetcode.sortlist;
public class Solution1 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        int len = getListSize(head);
        mergerSort(head, 0, len-1);
        return head;
    }
    public void mergerSort(ListNode head, int left, int right){
        int mid = (right+left) / 2;
        if (left == right)
            return;
        else{
            int first = left;
            int last = right;
            mergerSort(head, first, mid);
            mergerSort(head, mid+1, last);
            mergerListNode(head, first, mid, last);
        }
    }
   public void mergerListNode(ListNode head, int left,int mid,int right){
        int left1 = 0;
        int right1 = mid - left;
        int left2 = 0;
        int right2 = right - mid - 1;
        int k = 0;
        ListNode node1 = getListNode(head, left);
        ListNode node2 = getListNode(head, mid+1);
        int[] temp = new int[right - left + 1];
        while (left1 <= right1 && left2 <= right2){
            ListNode temp1 = getListNode(node1, left1);
            ListNode temp2 = getListNode(node2, left2);
            if (temp1.val < temp2.val){
                temp[k++] = temp1.val;
                left1++;
            }else{
                temp[k++] = temp2.val;
                left2++;
            }
        }
        while (left1 <= right1){
            temp[k++] = getListNode(node1, left1).val;
            left1++;
        }
        while (left2 <= right2){
            temp[k++] = getListNode(node2, left2).val;
            left2++;
        }
        for (int i=0; i<k; ++i){
            getListNode(head, i + left).val = temp[i];
        }
    }
    public ListNode getListNode(ListNode head, int index){
        ListNode temp = head;
        for (int i=0; i<index; ++i){
            temp = temp.next;
        }
        return temp;
    }
    public int getListSize(ListNode head){
        int len = 0;
        while (head != null){
            len++;
            head = head.next;
        }
        return len;
    }
    public static void main(String[] args) {
        ListNode head1 = new ListNode(10);
        ListNode head2 = new ListNode(40);
        ListNode head3 = new ListNode(6);
        ListNode head4 = new ListNode(22);
        ListNode head5 = new ListNode(1);
        ListNode head6 = new ListNode(30);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        head5.next = head6;
        head6.next = null;
        Solution1 solution = new Solution1();
        solution.sortList(head1);
        while (head1 != null){
            System.out.println(head1.val);
            head1 = head1.next;
        }
    }
}

下面是AC的代码：

package cn.xym.leetcode.sortlist;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        int len = getSize(head);
        ListNode list = mergerSort(head,len);
        return list;
    }
    public ListNode mergerSort(ListNode head, int len) {
        if (len == 1)
            return head;
        //找出当前head链表中间的ListNode
        int middle = len / 2;
        ListNode preMiddleNode = getListNode(head, middle-1);
        ListNode endNode = getListNode(head, len-1);
        ListNode middleNode = preMiddleNode.next;
        preMiddleNode.next = null;
        endNode.next = null;
        int leftLen = getSize(head);
        int rightLen = getSize(middleNode);
        ListNode leftList = mergerSort(head, leftLen);
        ListNode rightList = mergerSort(middleNode, rightLen);
        ListNode allList = mergerListNode(leftList, rightList);
        return allList;
    }
    /*返回一个局部排序好的表*/
    public ListNode mergerListNode(ListNode left, ListNode right) {
        ListNode temp = new ListNode(Integer.MIN_VALUE);
        ListNode preHead = new ListNode(Integer.MIN_VALUE);
        preHead = temp;
        //两个排序好的链表进行合并
        while (left != null && right != null){
            if (left.val < right.val){
                temp.next = left;
                left = left.next;
            }else{
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left == null){
            temp.next = right;
        }
        if (right == null){
            temp.next = left;
        }
        return preHead.next;
    }
    public ListNode getListNode(ListNode head, int index) {
        ListNode temp = head;
        for (int i = 0; i < index; ++i) {
            temp = temp.next;
        }
        return temp;
    }
    public int getSize(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
    public static void main(String[] args) {
        ListNode head1 = new ListNode(10);
        ListNode head2 = new ListNode(40);
        ListNode head3 = new ListNode(6);
        ListNode head4 = new ListNode(22);
        ListNode head5 = new ListNode(1);
        ListNode head6 = new ListNode(30);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        head5.next = head6;
        head6.next = null;
        Solution solution = new Solution();
        head1 = solution.sortList(head1);
        while (head1 != null) {
            System.out.println(head1.val);
            head1 = head1.next;
        }
    }
}