We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Sort List

Difficulty: Medium

Problem Description

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

Key Insights

The problem requires sorting a linked list, which cannot be accessed randomly like arrays.
A common approach to sort linked lists is to use Merge Sort due to its efficiency and ability to work with linked structures.
Sorting should ideally be done in O(n log n) time complexity, and O(1) space complexity is desired in the follow-up.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(1) (for the sorting algorithm itself, if implemented iteratively)

Solution

To solve the problem, we can use the Merge Sort algorithm. This involves the following steps:

Base Case: If the list is empty or has only one node, it is already sorted.
Splitting the List: Use the fast and slow pointer technique to find the middle of the list, which allows us to split the list into two halves.
Recursively Sort: Sort each half of the list recursively.
Merge: Merge the two sorted halves back together.

This approach works efficiently with linked lists due to the nature of merging sorted lists, which can be done in linear time.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    # Function to split the linked list into two halves
    def split(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return head, slow

    # Function to merge two sorted linked lists
    def merge(left, right):
        if not left:
            return right
        if not right:
            return left
        if left.val < right.val:
            left.next = merge(left.next, right)
            return left
        else:
            right.next = merge(left, right.next)
            return right

    # Split the list into two halves
    left, right = split(head)
    
    # Sort each half recursively
    left = sortList(left)
    right = sortList(right)

    # Merge the sorted halves
    return merge(left, right)

← Back to All Questions