Sort List

Source

• lintcode: Sort List

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

Example
Given 1-3->2->null, sort it to 1->2->3->null.

详解

Java

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    public ListNode sortList(ListNode head){
        if(head==null || head.next==null) return head;
        //find middle
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=null;
        while(fast!=null && fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }

        //pre不可能为null
        //因为pre为null的情况只能是head.next==null但是这种情况已经在最开始返回了
        pre.next=null;

        ListNode left = sortList(head);
        ListNode right = sortList(slow);

        return merge(left, right);
    }

    public ListNode merge(ListNode left, ListNode right){
        ListNode head = new ListNode(0);
        ListNode tail=head;

        while(left!=null && right!=null){
            ListNode node=null;
            if(left.val<right.val){
                node = left;
                left=left.next;
            }
            else{
                node=right;
                right=right.next;
            }
            node.next=null;
            tail.next=node;
            tail=tail.next;
        }
        if(left==null){
            tail.next=right;
        }
        else{
            tail.next=left;
        }
        return head.next;
    }
}