[LintCode] 98 Sort List 解题报告

Description
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.


Challenge
Solve it by merge sort & quick sort separately.



思路
解法一：
merge sort
把链表从当中劈开，sort左边，sort右边，merge。

Code

/**
 * 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) {  
        // write your code here
        
        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);
    }
    
    public ListNode findMid(ListNode head) {
        
        ListNode slow;
        ListNode fast;
        
        slow = head;
        fast = head.next;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }
    
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            }
            else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        if (l1 != null) {
            curr.next = l1;
        }
        else {
            curr.next = l2;
        }
        
        return dummy.next;
    }
}

解法二：

quicksort

把链表分成三份：比head.val小的，比head.val大的，和head.val相等的。

把前两个链表quicksort，然后把这三个接起来。

Code

/**
 * 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) {  
        // write your code here
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode lessDummy = new ListNode(0);
        ListNode less = lessDummy;
        ListNode greaterDummy = new ListNode(0);
        ListNode greater = greaterDummy;
        ListNode equal = head;
        ListNode curr = head.next;
        while (curr != null) {
            if (curr.val < head.val) {
                less.next = curr;
                less = less.next;
            }
            else if (curr.val > head.val) {
                greater.next = curr;
                greater = greater.next;
            }
            else { // curr.val == head.val
                equal.next = curr;
                equal = equal.next;
            }
            curr = curr.next;
        }
        less.next = null;
        greater.next = null;
        equal.next = null;
        
        lessDummy.next = sortList(lessDummy.next);
        greaterDummy.next = sortList(greaterDummy.next);
        
        ListNode dummy = lessDummy;
        curr = dummy;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = head;
        equal.next = greaterDummy.next;
        
        return dummy.next;
    }
}