Sort a linked list in O(n log n) time using constant space complexity.
对于O(nlogn)的排序,无非是merge sort,quick sort和heap sort。这里使用merge sort的递归解法,因为使用了递归,所以严格意义上来说利用了额外的栈空间,但是迭代解法实在是很麻烦,代码不容易懂,这里就不讨论了。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode walker = head; ListNode runner = head; while(runner.next!=null && runner.next.next!=null) { walker = walker.next; runner = runner.next.next; } ListNode head2 = walker.next; walker.next = null; ListNode head1 = head; head1 = sortList(head1); head2 = sortList(head2); return merge(head1, head2); } private ListNode merge(ListNode head1, ListNode head2) { ListNode helper = new ListNode(0); helper.next = head1; ListNode pre = helper; while(head1!=null && head2!=null) { if(head1.val<head2.val) { head1 = head1.next; } else { ListNode next = head2.next; head2.next = pre.next; pre.next = head2; head2 = next; } pre = pre.next; } if(head2!=null) { pre.next = head2; } return helper.next; } }
Advertisements