Sort a linked list in O(n log n) time using constant space complexity.
Have you met this question in a real interview?
Yes
Example
Given 1-3->2->null, sort it to 1->2->3->null.
MERGE SORT:
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The head of linked list.
* @return: You should return the head of the sorted linked list,
using constant space complexity.
*/
public ListNode sortList(ListNode head) {
// write your code here
if(head == null || head.next == null){
return head;
}
ListNode midNode = findMid(head);
ListNode right = sortList(midNode.next);
midNode.next = null;
ListNode left = sortList(head);
return merge(left, right);
}
private ListNode findMid(ListNode head){
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
private ListNode merge(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 != null){
cur.next = l1;
}
if(l2 != null){
cur.next = l2;
}
return dummy.next;
}
}
QuickSort:
No comments:
Post a Comment