[Coderust] Sort a Linked List Using Merge Sort

 

 

Problem

 

 

 

 

---

 

Solution

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # find the middle of the linked list
        # https://leetcode.com/problems/middle-of-the-linked-list/
        slow = head
        fast = head.next
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        # divide the list into two parts
        head2 = slow.next
        slow.next = None
        
        # keep dividing
        head = self.sortList(head)
        head2 = self.sortList(head2)
        
        return self.merge(head, head2)
    
    
    # from Merge Two Sorted Linked Lists problem
    def merge(self, head, head2):
        if not head or not head2:
            return head or head2
        
        dummy = curr = ListNode(0)
        
        while head and head2:
            if head.val <= head2.val:
                curr.next = head
                head = head.next
            else:
                curr.next = head2
                head2 = head2.next
            curr = curr.next
        
        if head or head2:
            curr.next = head or head2
        
        return dummy.next

Time Complexity

O(N logN)

 

 

Space Complexity

O(N)