Merge Sort Doubly Linked List
MediumPremium
You are given the head of a doubly linked list. Write a function to sort the linked list in either ascending or descending order using merge sort.
Constraints
- You must implement the sorting algorithm using the merge sort technique.
- The sorting should be performed in-place, i.e., do not create a new list.
- You can assume the input list is non-empty.
Example
input: Doubly Linked List [1, 3, 2], ascending output: [1, 2, 3] input: Doubly Linked List [1, 3, 2], descending output: [3, 2, 1]
To solve this problem, we'll follow these steps:
- Base Case: If the list is empty or contains only one element, it is already sorted. Return the head of the list.
- Find the Middle: Use the slow and fast pointer technique to find the middle of the list.
- Split the List: Divide the list into two halves from the middle.
- Sort Each Half: Recursively sort both halves.
- Merge Sorted Halves: Merge the two sorted halves into a single sorted list. Depending on the
ascendingparameter, merge the lists in ascending or descending order. - Return the Head: Return the head of the newly sorted list.
Here's the implementation:
from typing import Optional
class Node:
def __init__(self, val: int, prev: Optional['Node'] = None, next: Optional['Node'] = None):
self.val = val
self.prev = prev
self.next = next
def merge_sort_doubly_linked_list(head: Optional[Node], ascending: bool) -> Optional[Node]:
if not head or not head.next:
return head
# Split the list into two halves
mid = split(head)
# Recursively sort each half
left = merge_sort_doubly_linked_list(head, ascending)
right = merge_sort_doubly_linked_list(mid, ascending)
# Merge the sorted halves
return merge(left, right, ascending)
def split(head: Optional[Node]) -> Optional[Node]:
if not head:
return head
slow = head
fast = head
# Use two pointers to find the middle
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# Disconnect the two halves
mid = slow
if slow.prev:
slow.prev.next = None
slow.prev = None
return mid
def merge(left: Optional[Node], right: Optional[Node], ascending: bool) -> Optional[Node]:
dummy = Node(0)
tail = dummy
while left and right:
if (ascending and left.val <= right.val) or (not ascending and left.val >= right.val):
tail.next = left
left.prev = tail
left = left.next
else:
tail.next = right
right.prev = tail
right = right.next
tail = tail.next
if left:
tail.next = left
left.prev = tail
if right:
tail.next = right
right.prev = tail
# Return the head of the merged list
dummy.next.prev = None
return dummy.nextTime Complexity: The merge sort algorithm processes each element of the list n times. Thus, the time complexity is O(n log n), where n is the number of nodes in the list.
Space Complexity: The algorithm sorts the list in-place and uses a constant amount of extra space. Thus, the space complexity is O(1).
Watch Josh, a Software Engineer @ TikTok merge sort a doubly linked list.
Algorithm: