力扣148. 排序链表（归并排序）

力扣148. 排序链表

在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0 输出: -1->0->3->4->5

分析

题目要求时间复杂度是O(nlogn)，就需要二分，既然是二分，就确定了归并排序。

空间复杂度要求O(1)，就不能使用递归，并且不能创建额外的空间来保存临时数组。

题目是对链表进行排序，链表可以通过指针指向新节点进行排序，所以实现了O(1)的空间复杂度。

既然不能用递归，就根据递归的思想，从底向上进行归并。

第一轮循环，我们处理没两个节点，将节点两两排序。

第二轮循环，现在节点是两两有序，我们就每四个进行排序。

直到我们的排序规模超过了链表长度，就说明链表全部有序。

原链表： 4 -> 2 ||-> 1 -> 3 第一轮排序后： 2 -> 4 ||-> 1 -> 3 第二轮排序： 1 -> 2 -> 3 -> 4 原链表： -1 -> 5 ||-> 3 -> 4|| -> 0 第一轮排序后: -1 -> 5 || -> 3 -> 4 || -> 0 第二轮排序后： -1 -> 3 -> 4 -> 5 || -> 0 第三轮排序后： -1 -> 0 -> 3 -> 4 -> 5

注意：

寻找每两个待合并的链表时，要时刻注意越界问题。链表1可能长度不够排序规模，链表2也可能不够排序规模。

代码

/** * 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; } //统计链表长度 int len = 0; ListNode tmp = head; while(tmp != null){ len++; tmp = tmp.next; } //System.out.println("链表长度为："+len); //创建虚假头节点 ListNode dumHead = new ListNode(0); dumHead.next = head; //sortLen是每次合并的链表的规模, //从每次合并两个单节点开始，第二次合并两个长度为2的节点，第三次合并两个长度为8的节点，直到合并完毕。 int sortLen = 1; while(sortLen<len){ ListNode pre = dumHead; ListNode h = dumHead.next; //找待合并的两个链表的头结h1和h2 while(h!=null){ //h1就是当前头结点 ListNode h1 = h; //寻找h2 int i = sortLen; while(i>0){ if(h == null) break; h = h.next; i--; //System.out.println(i); } //如果i>0，说明h1这个长度还没有待合并的长度长，所以肯定h2不存在。 if(i>0) break; ListNode h2 = h; //将h移动到h2这一段链表后面 i = sortLen; while(i>0){ if(h == null) break; h = h.next; i--; } // 求出两个链表的长度 //h1完整地走完了一个sortLen，所以长度就是sortLen int c1 = sortLen; //h2不一定走完了sortLen，所以长度是sortLen-i int c2 = sortLen - i; //合并h1和h2 /* 4->2 h1 h2 */ //先合并前面长度相同的一部分 //pre节点在h1之前，保存到现在就是为了合并时能将h1和h2合并后的链表和前面的连接在一起。 while(c1 > 0 && c2 > 0) { if(h1.val < h2.val) { pre.next = h1; h1 = h1.next; c1--; }else { pre.next = h2; h2 = h2.next; c2--; } //既然排序了一个数字，那么pre就可以往后挪了。 pre = pre.next; } //如果h1或者h2还没排序完，接着排序尾巴 //将pre指向尾巴 pre.next = c1 > 0 ? h1 : h2; //将pre指向尾巴的末尾。 while(c1 > 0 || c2 > 0) { pre = pre.next; c1--; c2--; } //合并完成，将pre指向下一个准备排序的头节点，直到这一趟走完，h指向了null。 pre.next = h; } //一轮排序结束，合并规模翻倍。 sortLen*=2; //合并规模超过了总长度，结束。 } return dumHead.next; } }