Sort List

链表排序

题目

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

解析重点

1.既然涉及到排序，那我们肯定使用常见的排序算法，速度快的我们一般选择归并排序。
2.归并排序涉及到数据切分，那么我们怎么把链表分为两部分呢？这里我们使用快慢指针，将数据切为两部分。递归调用即可。
3.数据切分完后，涉及到合并切分完后的数据。这里切分完后得到是两个有序链表，那么我只需要合并两个有序链表即可，同样
是递归调用。

java代码

整个代码和归并排序比较相似，如果不能理解可以先去看看归并排序。

/**
 * 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;
        
    // step 1. cut the list to two halves
    ListNode prev = null, slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
      prev = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    
	//这里将链表彻底划分为两个部分
    prev.next = null;
    
    // step 2. sort each half
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // step 3. merge l1 and l2
    return merge(l1, l2);
  }
  //合并两个有序链表
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0), cur = head;
    
	//循环比较两个链表第一个元素
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        cur.next = l1;
        l1 = l1.next;
      } else {
        cur.next = l2;
        l2 = l2.next;
      }
      cur = cur.next;
    }
    
	//合并第一个链表剩余节点到主链表
    if (l1 != null)
      cur.next = l1;
    
	//合并第二个链表到主链表
    if (l2 != null)
      cur.next = l2;
    
    return head.next;
  }

}