2014年4月29日 星期二

[LeetCode] Sort List

Problem:
Sort a linked list in O(n log n) time using constant space complexity.
Solution:O(nlogn)
public class Solution { public ListNode sortList(ListNode head) { if (head==null||head.next==null){ return head; } ListNode fast=head; ListNode slow=head; while(fast.next!=null && fast.next.next!=null){ fast=fast.next.next; slow=slow.next; } ListNode right=slow.next; slow.next=null; ListNode left=head; left =sortList(left); right=sortList(right); return merge(left, right); } public ListNode merge(ListNode left, ListNode right){ if (left==null){ return right; } if (right==null){ return left; } ListNode dummy=new ListNode(-1); ListNode end=dummy; while (left!=null && right!=null){ if (left.val<right.val){ end.next=left; left=left.next; } else{ end.next=right; right=right.next; } end=end.next; } if (left!=null){ end.next=left; } if (right!=null){ end.next=right; } return dummy.next; } }

沒有留言:

張貼留言