题目
链接
题解
从顶向下归并排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sort(head, null);
}
/**
* 快慢指针搭配找到中点
* 分治中点两边的链表
*/
private ListNode sort(ListNode head, ListNode tail) {
if (head == null) {
return head;
}
// 当头的下一个就是尾，将节点孤立返回
if (head.next == tail) {
head.next = null;
return head;
}
// 双指针快慢遍历找到中点
ListNode fast = head, slow = head;
while (fast != tail) {
fast = fast.next;
slow = slow.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
// 分治左右
ListNode l1 = sort(head, mid);
ListNode l2 = sort(mid, tail);
// 将分治结果合并成一个链表
ListNode res = merge(l1, l2);
return res;
}
/**
* 合并两个联表
*/
private ListNode merge(ListNode l1, ListNode l2) {
ListNode mergeList = new ListNode(0);
ListNode p = mergeList;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) {
p.next = l1;
} else {
p.next = l2;
}
return mergeList.next;
}
}