148. [M] Sort List

https://leetcode.com/problems/sort-list/

要在 O(nlogn) 的复杂度完成排序,必然要用折半的方法。

用递归解决,基本思想是,根据长度从中间拆成两个链表,递归对这两个链表排序,然后合并两个已经排序的链表。由于拆分过程最终会拆到长度为 1 的链表,因此排序实际上是在合并的过程中完成的。

class Solution {
public int listLength(ListNode head) {
int len = 0;
while (head != null) {
head = head.next;
len++;
}
return len;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
int len = listLength(head);
ListNode a = head;
for (int i = 0; i < len / 2 - 1; i++) {
head = head.next;
}
ListNode b = head.next;
head.next = null;
a = this.sortList(a);
b = this.sortList(b);
return mergeList(a, b);
}
public ListNode mergeList(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while (a != null && b != null) {
if (a.val < b.val) {
head.next = a;
a = a.next;
} else {
head.next = b;
b = b.next;
}
head = head.next;
}
if (a != null) {
head.next = a;
} else {
head.next = b;
}
return dummy.next;
}
}