148. Sort List.md

148. Sort List

Question:

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Thinking:

• Method1:
  • 并归排序，自顶向下。
  • 参考Merge。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head, fast = head, temp = null;
        while(fast != null && fast.next != null){
            temp = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        temp.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }
    private static ListNode merge(ListNode node1, ListNode node2){
        ListNode dummy = new ListNode(0);
        ListNode result = dummy;
        while(node1 != null || node2 != null){
            if(node1 == null){
                dummy.next = node2;
                node2 = node2.next;
            }else if(node2 == null){
                dummy.next = node1;
                node1 = node1.next;
            }else if(node1.val <= node2.val){
                dummy.next = node1;
                node1 = node1.next;
            }else{
                dummy.next = node2;
                node2 = node2.next;
            }
            dummy = dummy.next;
        }
        return result.next;
    }
}

二刷

1. 一开始的想法是用快排做这道题，但是由于这是一个单向链表，所以反向遍历势必不可能到达题目中要求的O(NlogN)。
2. 所以和快排类似的并归排序可以满足这个要求并且可以不用反向遍历单向链表。
3. 自顶向下的并归排序是一种分治的体现。首先将大任务分配到不可分割的地步（就是ForkJoin框架中不可分割的子任务），这就是Fork，在将基础逻辑应用在每个子任务上。对于并归排序而言，必须要将所有的子任务合成起来，就是是Join。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head1 = slow.next;
        slow.next = null;
        head = sortList(head);  //分割任务Fork
        head1 = sortList(head1); //分割任务Fork
        return merge(head, head1);  //合并任务Join
    }
    private ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy, cur1 = l1, cur2 = l2;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            }else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if(cur1 != null || cur2 != null){
            cur.next = (cur1 != null) ? cur1 : cur2;
        }
        return dummy.next;
    }
}

Third Time

• Method 1: Divide and conquer

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
   class Solution {
   	public ListNode sortList(ListNode head) {
   		if(head == null || head.next == null) return head;
   		ListNode dummy = new ListNode(0);
   		dummy.next = head;
   		ListNode slow = dummy, fast = dummy;
   		while(fast != null && fast.next != null){
   			slow = slow.next;
   			fast = fast.next.next;
   		}
   		ListNode second = slow.next;
   		slow.next = null;
   		ListNode l1 = sortList(head);
   		ListNode l2 = sortList(second);
   		return merge(l1, l2);
   	}
   	private ListNode merge(ListNode l1, ListNode l2){        
   		ListNode dummy = new ListNode(0), cur = dummy;
   		while(l1 != null || l2 != null){
   			if(l1 != null && l2 != null){
   				cur.next = l1.val <= l2.val ? l1: l2;
   				if(l1.val <= l2.val) l1 = l1.next;
   				else l2 = l2.next;
   			}else if(l1 != null){
   				cur.next = l1;
   				break;
   			}else{
   				cur.next = l2;
   				break;
   			}
   			cur = cur.next;
   		}
   		return dummy.next;
   	}
   }