在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// 0个节点 || 1个节点
if (head == null || head.next == null) {
return head;
}
// >= 2个节点
ListNode first = head, second = null, mid = getMid(head);
second = mid.next;
mid.next = null; //将链表分为两段!!!!
//递归
first = sortList(first);
second = sortList(second);
return merge(first, second);
}
//排序
ListNode merge(ListNode first, ListNode second) {
if (first == null) {
return second;
}
if (second == null) {
return first;
}
ListNode res = new ListNode(0);
ListNode curr = res; //控制新链表顺序的point
while (first != null && second != null) {
if (first.val < second.val) {
curr.next = first;
curr = curr.next;
first = first.next;
} else {
curr.next = second;
curr = curr.next;
second = second.next;
}
}
if (first != null) {
curr.next = first;
}
if (second != null){
curr.next = second;
}
return res.next;
}
//将链表平分为两段,返回第一段末尾 例如:5个点返回2号点,6个点返回3号点
ListNode getMid(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Q.E.D.