**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..-**

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

__________________________________________________

### Like this:

Like Loading...

*Related*