Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Merge Sort in a Linked list

Objec­tive: Given a Linked List, Sort it using merge sort.
Exam­ple:

->9->3->4->2->5->1

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

Approach:

Ref­er­ence : 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 point­ing at the mid­dle of the list.
  • Make new pointer, new­Head = oldHead.next.
  • Now oldHead.next = null.
  • Now do old­Head = head;
  • Now at this point, list is divided into two parts, with old https://algorithms.tutorialhorizon.com/wp-admin/post-new.phpHead and new­Head is point­ing at the start of the linked list.
  • Now recur­sively solve these two parts and merge them into sin­gle sorted list.
  • Click here to see “How to merge two sorted Linked Lists”.

Com­plete Code:


Out­put:

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

You may also like...