Merge Sort in a Linked list

Objective: Given a Linked List, Sort it using merge sort.
Example:

->9->3->4->2->5->1
Sorted List: ->1->2->3->4->5->9

Approach:

Reference : Merge Sort in array

  • As it Merge sort, we apply the same logic , Divide and Conquer.
  • Find the length of the link list, say it is L.
  • mid will be L/2.
  • Now we need to divide the List into two equal parts.
  • Take pointer(oldHead) and move it by L/2. Now it is pointing at the middle of the list.
  • Make new pointer, newHead = oldHead.next.
  • Now oldHead.next = null.
  • Now do oldHead = head;
  • Now at this point, list is divided into two parts, with old https://algorithms.tutorialhorizon.com/wp-admin/post-new.phpHead and newHead is pointing at the start of the linked list.
  • Now recursively solve these two parts and merge them into single sorted list.
  • Click here to see “How to merge two sorted Linked Lists“.

Complete Code:


Output:

->9->3->4->2->5->1
 Sorted List: 
->1->2->3->4->5->9

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: