Sorting algorithms are frequently asked during a technical interview. Several common sorting algorithms such as quicksort, selection sort, merge sort are usually applied to sorting a list. However, sorting a linked list is not straightforward: it’s not easy to access an element by index in constant running time. Most of the sorting algorithms ask for extra space and the running time is relatively large. Today, I’ll talk about how to apply the merge sort algorithm to a linked list, the running time is O(n*log(n)), and it happens in-place.
What is Merge Sort?
Merge sort is a divide and conquer algorithm that sorts the input list recursively. There are two steps to finish the process:
- Divide the input list into n sub-list, each sub-list has the same size.
- Merge the sub-lists into one big list, and each element in the list is ordered.
Here’s a picture illustrating the process:
As we can see from the picture, there are two key steps to sort a list: 1). divide a list evenly; 2).merge the sub-list in the end. I’ll talk about how to achieve these functions in a linked list.
How to divide a linked list into two parts?
The most intuitive way is to count the total_size of the linked list, then divide the linked list into two parts, each part has the size of total_size / 2. However, we found it takes O(n) time to run because we must iterate the whole linked list in the beginning. The more efficient way is applying two-pointers approaching. Assume we have two pointers: a fast pointer and a slow pointer. In each step, the fast pointer steps across two nodes, the slow pointer only steps across one node. When the fast node approaches the end of the list, the slow pointer is actually standing at the middle point of the linked list. Let’s prove it together:
Assume given list has n nodes, both fast pointer and slow pointer stand at the first node of the list.
fast pointer: rate is 2 node/step, take n/2 steps to visit all nodes;
slow pointer: rate is 1 node/step, take n steps to visit all nodes. At the n/2 steps: fast pointer stands at the last node of the list, slow pointer now at n/2 steps * 1 node/step = n/2 node. Is exactly the middle node of the size n linked list.
How to merge two linked lists in ascending order?
Assume we have two sorted linked lists, we want to merge them as a big sorted list. We can have two pointers to indicate the node we’re currently comparing, and append the smaller node into the new node. Let’s see how it works:
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6We start from the first node from the list, i'll mark the current compareing nodes bold. l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 ->
Comparision: 1 < 2, append 1 to the result, move the pointer to its next l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 ->
Comparision: 2 < 3, append 2 to the result, move the pointer to its nextl1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 -> 3
Comparision: 3 < 4, append 3 to the result, move the pointer to its nextl1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 -> 3 -> 4
Comparision: 4 < 5, append 4 to the result, move the pointer to its nextl1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 -> 3 -> 4 -> 5
Comparision: 5 < 6, append 5 to the result, since l1’s pointer meets the end, we simply append all the following nodes after l2’s pointer to the result: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Merge sort a linked list
Now it’s time to build the whole solution with previous key functions. Remember it’s a divide and conquer algorithm, recursion may happen in many places!
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next #main function
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
second = self.break_half(head)
sorted_first = self.sortList(head)
sorted_second = self.sortList(second)
return self.merge(sorted_first, sorted_second)
#will divide the list into two parts evenly, and return the head of the second half
def break_half(self, head):
if not head or not head.next:
return head slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
mid = slow.next
slow.next = None
return mid #merge two list into a big ordered list
def merge(self, l1, l2):
if not l1 and not l2:
return None
if not l1:
return l2
if not l2:
return l1
new_head = None
if l1.val < l2.val:
new_head = l1
new_head.next = self.merge(l1.next, l2)
else:
new_head = l2
new_head.next = self.merge(l1, l2.next)
return new_head
Analyze:
- Time Complexity:
O(nlogn), where n is the number of nodes in the linked list. - Space Complexity:
O(nlogn), where n is the number of nodes in the linked list. Since the problem is recursive, we need additional space to store the recursive call stack. The maximum depth of the recursion tree isO(nlogn).
