700538. Merge Sort on Doubly Linked List
Hard
Merge Sort on Doubly Linked List
Slug: merge-sort-on-doubly-linked-list
Difficulty: Hard
Topic Tags: doubly-linked-list, Linked List, Sorting, Merge Sort, Data Structures, Algorithms
Company Tags: None
Summary
The problem is to sort a doubly linked list using the merge sort algorithm. The key concepts involved are sorting, doubly linked lists, and the merge sort algorithm.
Detailed Explanation
To solve this problem, we will follow the standard merge sort algorithm approach:
- Divide the input list into two halves until each half has one element.
- Recursively sort both halves.
- Merge the sorted halves to produce a single sorted list.
Since it's a doubly linked list, we need to take care of updating the next and prev pointers correctly during the merge process.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
leftandright, to point to the start and end of the input list. - Recursively divide the list into two halves until each half has one element.
- For each level of recursion:
- Merge the left and right halves in a bottom-up manner.
- Compare the smallest unmerged elements from both halves and move the smaller one to the front of the result.
- Update the
nextandprevpointers accordingly.
- Merge the left and right halves in a bottom-up manner.
- Continue merging until the entire list is sorted.
Optimized Solutions
Here are optimized solutions in various programming languages:
Java
public class MergeSortDoublyLinkedList {
public static Node mergeSort(Node head) {
if (head == null || head.next == null) {
return head;
}
Node prev = null;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
Node mid = slow;
Node right = mid.next;
mid.next = null;
Node sortedLeft = mergeSort(head);
Node sortedRight = mergeSort(right);
return merge(sortedLeft, sortedRight);
}
public static Node merge(Node left, Node right) {
if (left == null) {
return right;
}
if (right == null) {
return left;
}
Node result;
if (left.data <= right.data) {
result = left;
left = left.next;
} else {
result = right;
right = right.next;
}
while (left != null && right != null) {
if (left.data <= right.data) {
result.next = left;
left = left.next;
} else {
result.next = right;
right = right.next;
}
result = result.next;
}
if (left != null) {
result.next = left;
} else {
result.next = right;
}
return result;
}
}