Teaching Kids Programming – Sorting a Linked List using Merge Sort (Divide and Conquer)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a singly linked list of integers node, sort the nodes by their values in ascending order.

Constraints
n ≤ 100,000 where n is the number of nodes in node
Example 1
Input
Visualize
node = [14, 13, 10]
Output
Visualize
[10, 13, 14]

Merge Sorting a Linked List (Divide and Conquer Technique)

Given a Linked List, we can find the middle of the linked list using fast and slow pointer, disconnect the linked list at the middle point to make two sub linked lists. Recursively sort them and merge two linked list.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortLinkedList(self, node):

        def mid(head):
            if head is None or head.next is None:
                return head
            fast, slow = head, head
            prev = None
            while fast and fast.next:
                fast = fast.next.next
                prev = slow
                slow = slow.next
            prev.next = None            
            return slow

        def merge(a, b):
            dummy = LLNode(-1)
            p = dummy
            while a and b:
                if a.val < b.val:
                    p.next = a
                    a = a.next
                else:
                    p.next = b
                    b = b.next
                p = p.next
            if a:
                p.next = a
            if b:
                p.next = b
            return dummy.next

        if node is None or node.next is None:
            return node
        # Recursively sort the left linked list
        a = self.sortLinkedList(mid(node))
        # Recursively sort the right linked list
        b = self.sortLinkedList(node)
        return merge(a, b)

Merging two sorted linked lists is quite the same as merging two sorted lists. It requires O(N+M) time. Overall, the complexity of sorting a linked list is O(NLogN).

Sort List by Additional Space

However, we can copy the linked list to a list, sort the list in O(NLogN) and iterate the linked list to overwrite the values:

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def sortLinkedList(self, node):
        values = []
        head = node
        while node:
            values.append(node.val)
            node = node.next
        values.sort()
        values = collections.deque(values)
        node = head
        while node:
            node.val = values.popleft()
            node = node.next
        return head

See also: Teaching Kids Programming – MergeSort Simply Explained

–EOF (The Ultimate Computing & Technology Blog) —