# 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.
• 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.

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