题目：
Sort a linked list in O(n log n) time using constant space complexity.
分析：
排序一个链表。要求O(nlogn)时间，O(1)空间。
说到O(nlogn)时间，首先想到的是合并排序。虽然合并排序对于数组是O(n)空间，但是对于链表却可以做到O(1)空间。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
public class Solution { // Merge sort: O(nlogn) time, O(1) space public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode p1 = head; ListNode p2 = head.next; // Find the midpoint while(p2 != null && p2.next != null){ p1 = p1.next; p2 = p2.next.next; } p2 = sortList(p1.next); p1.next = null; p1 = sortList(head); return merge(p1, p2); } private ListNode merge(ListNode h1, ListNode h2){ ListNode fakeHead = new ListNode(Integer.MIN_VALUE); ListNode p = fakeHead; while(h1 != null && h2 != null){ if(h1.val < h2.val){ p.next = h1; h1 = h1.next; } else{ p.next = h2; h2 = h2.next; } p = p.next; } p.next = (h1 == null) ? h2 : h1; return fakeHead.next; } } |