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;
}
}
沒有留言:
張貼留言