LeetCode 148. 【Java】148. Sort List
原题链接
中等
作者:
tt2767
,
2020-03-18 17:58:32
,
所有人可见
,
阅读 640
/**
1. 自底向上的归并排序, 每次枚举待排序小段的长度,并合并相邻两个小段, 一直向上排序, 递归求法会使用O(logn)的系统空间
2. while (i < len && left != null) 注意追加时这里也要判断 left 是否为空
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
int n = 0;
for (ListNode p = head; p != null; p = p.next) n++;
ListNode dummy = new ListNode(0);
dummy.next = head;
// 这里必须是1, 是枚举一小段的长度, 否则如果长度为奇数会有剩余没有sort的元素
for (int len = 1 ; len < n ; len *= 2){
for (ListNode p = dummy; p.next != null ; p = sortSeg(p, len) )
;
}
return dummy.next;
}
public ListNode sortSeg(ListNode prev, int len){
ListNode left = prev.next, right = left;
for (int k = 0; k < len && right != null ; k++) right = right.next;
int i = 0 , j = 0;
while ( i < len && j < len && right != null){
if (left.val < right.val){
prev.next = left;
left = left.next;
i++;
} else {
prev.next = right;
right = right.next;
j++;
}
prev = prev.next;
}
while (i < len && left != null){
prev.next = left;
prev = prev.next;
left = left.next;
i++;
}
while (j < len && right != null){
prev.next = right;
prev = prev.next;
right = right.next;
j++;
}
prev.next = right;
return prev;
}
}