Merge Sort in a Linked list

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

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


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 =
  • Now = null.
  • Now do oldHead = head;
  • Now at this point, list is divided into two parts, with old 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“.



 Sorted List: 

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.