148. Sort List

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/sort-list
• topics: Divide and Conquer, Linked List

Description

Given the head of a linked list, return the list after sorting it in ascending order.

Idea

• Merge sort

Code

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # Split the list into two halves
        middle = self.getMiddle(head)
        right_head = middle.next
        middle.next = None 
        
        # Recursively sort both halves
        left_sorted = self.sortList(head)
        right_sorted = self.sortList(right_head)
        
        # Merge the two sorted halves
        return self.mergeSortedLists(left_sorted, right_sorted)
 
    def getMiddle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head.next 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
 
        return slow
 
    def mergeSortedLists(self, left: ListNode, right: ListNode) -> ListNode:
        dummy_head = ListNode(0)  # Dummy to simplify edge cases
        current = dummy_head
        while left and right:
            if left.val < right.val:
                current.next = left
                left = left.next
            else:
                current.next = right
                right = right.next
            current = current.next
 
        # Attach the remaining nodes 
        current.next = left if left else right
 
        return dummy_head.next