【刷题笔记10.5】LeetCode：排序链表

LeetCode：排序链表

一、题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

二、分析

这题咱们默认要求：空间复杂度为O(1)。所以这把咱们用自底向上的方法实现归并排序，则可以达到O(1) 的空间复杂度。

具体算法如下：

1、首先，判断如果所给的 head 为 null 则返回null
2、求出所给链表head的长度length，然后将链表拆分成子链表进行合并。具体算法如下：

• 2.1、用subLen表示每次需要排序的子链表的长度，初始值subLen为1.
• 2.2、每次将链表拆分成若干个长度为subLen的子链表（最后一个子链表的长度可以小于subLen），按照每两个子链表一组进行合并（通过使用合并两个有序链表的做法），合并后即可得到若干个长度为 subLen2 的有序子链表（最后一个子链表的长度可以小于 subLen2）。合并两个子链表仍然使用合并两个有序链表的做法。
• 2.3、将subLen的值加倍（通过位运算左移1位的方式），重复第2步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完毕。

如何保证每次合并后得到的子链表都是有序的呢？可以通过数学归纳法证明。

• 1、初始时subLen为1，每个长度为1的子链表都是有序的

• 2、如果每个长度为subLen的子链表已经有序，那么合并两个长度为subLen的子链表后，得到长度为subLen * 2
  的子链表，一定也是有序的。

• 3、当最后一个子链表的长度小于subLen时，该子链表也是有序的，合并两个链表之后得到的子链表一定也是有序的。

三、上代码

public class Deal11 {public ListNode sortList(ListNode head) {if (head == null) {return null;}//1、从头向后遍历链表，统计链表长度int length = 0;ListNode p = head;while(p != null) {length++;p=p.next;}//2、设定result用于记录最终返回结果，并对其进行最终的初始化ListNode result = new ListNode(-1);result.next = head;//3、将链表拆分成若干个长度为subLen的子链表，并按照没两个子链表一组进行合并for (int subLen = 1; subLen < length; subLen <<= 1) {//将subLen的值加倍（通过位运算左移1位的方式）ListNode pre = result;ListNode cur = result.next;   //用于记录拆分链表的位置while (cur != null) { //如果链表没有被拆完//3.1 拆分出链表1，其长度为subLenListNode head_1 = cur;    //第一个链表的头，即curfor (int i = 1; i < subLen && cur != null && cur.next != null; i++) {cur = cur.next;}//3.2 拆分出链表2，其长度也为subLenListNode head_2 = cur.next; //第二个链表的头，即第一个链表尾部的下一个位置cur.next = null; //断开第一个链表和第二个链表的连接cur = head_2;    //第二个链表的头重新赋给curfor (int i = 1; i < subLen && cur != null && cur.next != null; i++) {cur = cur.next;}//3.3 再次断开第二个链表的的连接ListNode next = null;if (cur != null) {next = cur.next;  //用于记录拆分完两个链表后结束的后序位置cur.next = null;}//3.4 合并两个有序链表head_1 和 head_2ListNode merge = mergeTwo(head_1, head_2);pre.next = merge;while (pre.next != null) {pre = pre.next;}cur = next;}}return result.next;}//合并两个有序链表public ListNode mergeTwo(ListNode head1, ListNode head2) {ListNode result = new ListNode(-1);ListNode p = result;ListNode p1 = head1;ListNode p2 = head2;while(p1 != null && p2 != null) {if (p1.val > p2.val) {p.next = p2;p2 = p2.next;} else {p.next = p1;p1 = p1.next;}p = p.next;}if (p1 == null) {p.next = p2;}if (p2 == null) {p.next = p1;}return result.next;}
}