/** * Sort a linked list in O(n log n) time using constant space complexity. * */ public class SortList { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } //解法一 : 歸並法 // 15 / 15 test cases passed. // Status: Accepted // Runtime: 310 ms // Submitted: 0 minutes ago //時間復雜度O(n * log(n)) 空間復雜度 O(1) public ListNode sortList(ListNode head) { if(head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head; //找到鏈表的中點位置 while(fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } fast = slow.next; //斷開鏈表 slow.next = null; ListNode list1 = sortList(head); ListNode list2 = sortList(fast); return mergeList(list1, list2); } //合並兩鏈表 public ListNode mergeList(ListNode head1, ListNode head2) { ListNode head = new ListNode(-1); ListNode last = head; while(head1 != null && head2 != null) { if(head1.val <= head2.val) { last.next = head1; head1 = head1.next; } else { last.next = head1; head1 = head1.next; } last = last.next; } if(head1 != null) last.next = head1; if(head2 != null) last.next = head2; return head.next; } //解法二 // 15 / 15 test cases passed. // Status: Accepted // Runtime: 709 ms // Submitted: 0 minutes ago // 對排序好的鏈表設置一個中點指針,如果待排的節點大於中點指針的值,則從中點開始尋找插入點,否則從表頭開始查找 //其實也沒降低時間復雜度 和暴力插排一樣 仍為O(n*n) 空間復雜度 O(1) public ListNode sortList1(ListNode head) { ListNode preHead = new ListNode(-1); ListNode last = null; ListNode cur = null; int preNum = 0, postNum = 0; while(head != null) { ListNode headNext = head.next; if(last != null && last.val <= head.val) { postNum ++; cur = last; } else { preNum ++; cur = preHead; } while(cur.next != null) { if(cur.next.val >= head.val) { break; } cur = cur.next; } if(last == null) { last = head; } ListNode curNext = cur.next; cur.next = head; cur.next.next = curNext; head = headNext; if(postNum > preNum) { last = last.next; } } return preHead.next; } public static void main(String[] args) { // TODO Auto-generated method stub } }