Sort a doubly linked list using merge sort.
Medium
Unlock detailed company stats for this questionUpgrade
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:
Time 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.
Interview experiences
1 sharedRelated questions
Merge two sorted linked listMerge k sorted linked lists.Implement a doubly linked list.Related courses
Course
Course
Course