Be the first user to complete this post

  • 0
 Add to List
Medium

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

  1. As it Merge sort, we apply the same logic , Divide and Conquer.
  2. Find the length of the link list, say it is L.
  3. mid will be L/2.
  4. Now we need to divide the List into two equal parts.
  5. Take pointer(oldHead) and move it by L/2. Now it is pointing at the middle of the list.
  6. Make new pointer, newHead = oldHead.next.
  7. Now oldHead.next = null.
  8. Now do oldHead = head;
  9. Now at this point, list is divided into two parts, with old Head and newHead is pointing at the start of the linked list.
  10. Now recursively solve these two parts and merge them into single sorted list.
  11. Click here to see "How to merge two sorted Linked Lists".

Code:


Output:

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

Also Read: