题目

题目

思路

时间复杂度是O(nlogn)的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是O()），其中最适合链表的排序算法是归并排序。
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用到栈空间，自顶向下归并排序的空间复杂度是O(logn)，如果要达到O(1)的空间复杂度，则需要使用自底向上的实现方式。

自顶向下归并排序

• 过程：

1. 找到链表的中点（快慢指针），以中点为分界，将链表拆分成两个子链表。
2. 对两个子链表分别排序
3. 将两个排序后的子链表合并，得到完整的排序后的链表

• 递归的终止条件：
  链表的节点个数小于或等于1
• 实现：

class Solution {
  public ListNode sortList(ListNode head) {
    return sortList(head);
  }
  public ListNode sort(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    ListNode head2 = slow.next;
    slow.next = null;
    return merge(sort(head), sort(head2));
  }
  
  public ListNode merge(ListNode head1, ListNode head2) {
    ListNode dummtHead = new ListNode(0);
    ListNode temp = dummyHead;
    ListNode temp1 = head1;
    ListNode temp2 = head2;
    while (temp1 != null && temp2 != null) {
      if (temp1.val <= temp2.val) {
        temp.next = temp1;
        temp1 = temp1.next;
      } else {
        temp.next = temp2;
        temp2 = temp2.next;
      }
      temp = temp.next;
    }
    if (temp1 != null) {
      temp.next = temp1;
    } else if (temp2 != null) {
      temp.next = temp2;
    }
    return dummyHead.next;
  }
}

自底向上归并排序

• 过程

1. 首先求得链表的长度length
2. 用subLength表示每次需要排序的子链表的长度，初识时subLength=1
3. 每次将链表拆分成若干个长度为subLength的子链表（最后一个子链表的长度可以小于subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为subLength x 2的有序子链表（最后一个子链表的长度可以小于subLength x 2）。
4. 将subLength的值加倍(左移)，重复第三步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完成

• 实现

class Solution {
  public ListNode sortList(ListNode head) {
    if (head == null) {
      return head;
    }
    // 首先从头向后遍历，统计链表长度
    int length = 0;
    ListNode node = head;
    while (node != null) {
      length++;
      node = node.next;
    }
    // 初始化
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    // 每次将链表拆分成若干个长度为subLength的子链表，并按照每两个子链表为一组进行合并
    for (int subLength = 1; subLength < length; subLength << 1) {
      // 记录准备分割、合并的起始位置
      ListNode cur = dummyNode.next;
      // 记录之前已合并完的链表结束位置
      ListNode prev = dummyNode;
      while (cur != null) {
        // 第1个链表的头
        ListNode head1 = curr;
        // 取长度为subLength的子链表
        for (int i = 1; i < subLength && cur.next != null; i++) {
          cur = cur.next;
        }
        // 第2个链表的头
        ListNode head2 = cur.next;
        // 断开两个链表的连接
        cur.next = null;
        cur = head2;
        // 取出第2个长度为subLength的子链表
        for (int i = 1; i < subLength && cur != null; i++) {
          cur = cur.next;
        }
        // 记录取出两个链表后剩下的链表位置
        ListNode next = null;
        if (cur != null) {
          next = cur.next;
          // 断开第二个子链表
          cur.next = null;
        }
        // 将合并后的链表与已合并的部分连接上
        prev.next =merge(head1, head2);
        // 更新prev到新的合并后的链表结束位置
        while (prev.next != null) {
          prev = prev.next;
        }
        // 更新cur到未合并到链表开始位置
        cur = next;
      } 
    }
    return dummyNode.next;
  }
}