Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
代码
Approach #1 Divide and Conquer
public class Solution {
public ListNode sortList (ListNode head) {
if (head == null | head.next == null) return head;
ListNode mid = findMid(head);
ListNode head1 = head;
ListNode head2 = mid.next;
mid.next = null; //
ListNode left = sortList(head1);
ListNode right = sortList(head2);
return merge(left, right);
}
public ListNode findMid(ListNode head){
if (head == null) return null;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while (head1 != null || head2 != null) {
int a = head1 == null ? Integer.MAX_VALUE : head1.val;
int b = head2 == null ? Integer.MAX_VALUE : head2.val;
if (a < b) {
head.next = new ListNode(a);
if (head1 != null) head1 = head1.next;
} else {
head.next = new ListNode(b);
if (head2 != null) head2 = head2.next;
}
head = head.next;
}
return dummy.next;
}
}