102. Merge Sort for Linked Lists (In-place Algorithm)

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:

the process involves dividing the list into smaller segments, sorting each segment individually, and then merging them back together in a sorted manner. Here's the description rewritten:

To implement Merge Sort on a linked list, we follow the Divide and Conquer approach:

1. Determine the length of the linked list, denoted as L.
2. Calculate the midpoint of the list, L/2.
3. Divide the list into two equal parts.
4. Move a pointer (oldHead) to the middle of the list by traversing L/2 nodes.
5. Create a new pointer (newHead) and set it to oldHead.next.
6. Set oldHead.next to null, effectively splitting the list into two parts.
7. Reset oldHead to the beginning of the original list.
8. At this stage, the list is divided into two parts, with oldHead and newHead pointing to the start of each segment.
9. Recursively apply Merge Sort to these two segments.
10. Merge the sorted segments back together into a single sorted list.
11. Click here to read How to merge two sorted Linked Lists

Output:

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

Reference: Merge Sort in array

Related Problems:

- All Paths from Top Left to Bottom Right in 2D Array Medium
- Reverse a linked list using stack Medium
- Quick Sort Implementation Medium
- Backtracking - Rat In A Maze Puzzle Hard
- Round Price Problem Hard