98. Sort List – Merge Sort nlogn

Leave a comment

May 16, 2016 by oneOokay

>>>Bulbasaur<<<

Sort a linked list in O(n log n) time using constant space complexity.

 

Merge Sort [O(nlogn)]

Step1: Get the middle list node using fast & slow pointer

  • slow = head; fast = head.next; while( fast != null && fast.next != null)
  • OR
  • slow = head; fast = head; while( fast.next != null && fast.next.next !=null)
  • return slow;

Step2: Use the middle list node to divide the list into HALF (until single list node)

  • Right LinkedList: (Handle RIGHT LinkedList FIRST)
    • head: mid.next;
  • Left LinkedList:
    • CLOSE THE END FIRST:  slow.next = null;
    • head: head;

Step3: Merge left list and right list according to the value, return head. (KEY function)

  • unknown head: using dummy node
  • while loop

public class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null)
{
return head;
}

ListNode mid = findMid(head);
ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);

return mergeList(left, right);
}

private ListNode findMid(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
private ListNode mergeList(ListNode head1, ListNode head2){
ListNode dummy = new ListNode(0);
ListNode node = dummy;
while(head1 != null && head2 != null){
if(head1.val < head2.val){
node.next = head1;
head1 = head1.next;
}
else{
node.next = head2;
head2 = head2.next;
}
node = node.next;
}
if(head1 != null){
node.next = head1;
}
else {
node.next = head2;
}
return dummy.next;
}
}

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: