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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class MergeSortLinkedList { | |

public Node MergeList(Node a, Node b) { | |

Node result = null; | |

if (a == null) | |

return b; | |

if (b == null) | |

return a; | |

if (a.data > b.data) { | |

result = b; | |

result.next = MergeList(a, b.next); | |

} else { | |

result = a; | |

result.next = MergeList(a.next, b); | |

} | |

return result; | |

} | |

public int getLength(Node a) { | |

int count = 0; | |

Node h = a; | |

while (h != null) { | |

count++; | |

h = h.next; | |

} | |

return count; | |

} | |

public Node mergeSort(Node a) { | |

Node oldHead = a; | |

// find the length of the linkedlist | |

int mid = getLength(a) / 2; | |

if (a.next == null) | |

return a; | |

// set one pointer to the beginning of the list and another at the next | |

// element after mid | |

while (mid – 1 > 0) { | |

oldHead = oldHead.next; | |

mid—; | |

} | |

Node newHead = oldHead.next;// make newHead points to the beginning of | |

// the second half of the list | |

oldHead.next = null;// break the list | |

oldHead = a;// make one pointer points at the beginning of the first | |

// half of the list | |

Node t1 = mergeSort(oldHead);//make recursive calls | |

Node t2 = mergeSort(newHead); | |

return MergeList(t1, t2); // merge the sorted lists | |

} | |

public void display(Node head) { | |

Node currNode = head; | |

while (currNode != null) { | |

System.out.print("->" + currNode.data); | |

currNode = currNode.next; | |

} | |

} | |

public static void main(String args[]) { | |

Node a = new Node(9); | |

a.next = new Node(3); | |

a.next.next = new Node(4); | |

a.next.next.next = new Node(2); | |

a.next.next.next.next = new Node(5); | |

a.next.next.next.next.next = new Node(1); | |

MergeSortLinkedList m = new MergeSortLinkedList(); | |

m.display(a); | |

Node x = m.mergeSort(a); | |

System.out.println("\n Sorted List: "); | |

m.display(x); | |

} | |

} | |

class Node { | |

public int data; | |

public Node next; | |

public Node(int data) { | |

this.data = data; | |

this.next = null; | |

} | |

} |

**Output**:

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