700523. Merge Sort for Linked List
Sort a Linked List
Summary
In this problem, we are given a linked list and asked to sort it using the merge sort algorithm. This is a medium-level difficulty problem that requires understanding of both linked lists and the merge sort algorithm.
Detailed Explanation
To solve this problem, we will use the merge sort algorithm, which is a divide-and-conquer approach. The idea behind merge sort is to divide the list into smaller sublists until each sublist contains only one element (in other words, they are sorted), then combine these sorted sublists back together to form the final sorted list.
Here's how it works:
- If the linked list has one or zero elements, return the original list because it's already sorted.
- Split the linked list into two halves of roughly equal length (or the remaining half if the size is odd).
- Recursively apply step 1 to each half until you have lists of size 1 (which are already sorted).
- Merge the sorted halves back together, maintaining the correct order.
Here's an ASCII art diagram illustrating this process:
+----------------+
| 5 -> 2 -> 8 -> 3 |
+----------------+
|
v
+---------------+ +---------------+
| 2 -> 1 | | 3 -> 4 -> 6 |
+---------------+ +---------------+
|
v
+---------------+ +---------------+
| 1 | | 4 |
| (sorted) | | (sorted) |
+---------------+ +---------------+
In this example, we start with a list of five elements. We split it into two halves: 2 -> 1 and 3 -> 4 -> 6. We then recursively apply the same process to each half until we have lists of size 1. Finally, we merge these sorted halves back together to form the final sorted list.
The time complexity of this algorithm is O(n log n), where n is the number of elements in the linked list. The space complexity is O(n) due to the recursive function calls and temporary arrays used during the merging process.
Optimized Solutions
Java
public class LinkedList {
public static Node mergeSort(Node head) {
if (head == null || head.next == null) {
return head;
}
Node mid = getMiddle(head);
Node nextToMid = mid.next;
mid.next = null;
Node left = mergeSort(head);
Node right = mergeSort(nextToMid);
return merge(left, right);
}
public static Node getMiddle(Node head) {
if (head == null) {
return head;
}
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static Node merge(Node a, Node b) {
if (a == null) {
return b;
} else if (b == null) {
return a;
}
if (a.data <= b.data) {
a.next = merge(a.next, b);
return a;
} else {
b.next = merge(a, b.next);
return b;
}
}
}