Merge Sort Doubly Linked List
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.
The getMiddle function uses the slow and fast pointer technique to find the middle of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.
Check out our lesson on the tortoise & hare (slow & fast pointer) approach to learn more about what it is and how to use it!
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: