148. Sort List

Medium

Problem:

Sort the linked list in $O(nlogn)$ time complexity.

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

https://leetcode.com/problems/sort-list

Solution:

Merge Sort

Due to its nature, it's difficult to arbitrarily designate a pivot in a linked list, so a fixed position must be chosen.

1. For the divide-and-conquer strategy of merge sort, the list should be split in the middle. However, since the total length of a linked list is unknown, we need to employ the Runner technique.

2. Using three variables, half, slow, and fast, move slow one step at a time and fast two steps at a time. When fast reaches the end, slow will be in the middle. At this point, set half to the value right before slow and cut off the linked list relationship based on the position of half.

3. Finally, compare the sizes of the divided items and merge them back together in a sorted manner.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1 or l2

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not (head and head.next):
            return head
        
        # Runner
        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next
        half.next = None
        
        # Divide and Conquer
        l1 = self.sortList(head)
        l2 = self.sortList(slow)
        
        return self.mergeTwoLists(l1, l2)

A practical method using built-in functions

If you need to write algorithms on a whiteboard during an interview, you should avoid this approach.

# 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]:
        elements = []
        node = head

        while node:
            elements.append(node.val)
            node = node.next
        
        elements.sort()

        node = head

        for idx in range(len(elements)):
           node.val = elements[idx]
           node = node.next

        return head