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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sort List

Number: 148

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon, Microsoft, TikTok, Apple, ByteDance, Yahoo, Adobe, Bloomberg

Problem Description

Given the head of a linked list, the task is to sort the list in ascending order and return the sorted list. The list can have up to 5 * 10⁴ nodes and values range between -10⁵ and 10⁵. The challenge is to perform the sort with O(n log n) time complexity and, if possible, O(1) space complexity.

Key Insights

  • Merge sort is well-suited for linked lists; it naturally relies on splitting the list and merging sorted sublists.
  • The slow and fast pointer technique is used to find the middle point of the list.
  • A recursive merge sort implementation may use O(log n) space for recursion stack. To achieve O(1) extra space, an iterative bottom-up merge sort approach would be preferred.
  • Merging two sorted lists is efficient with linked lists because of their sequential access.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(1) extra space for an iterative bottom-up approach (O(log n) for recursive calls if using recursion)

Solution

The solution employs the merge sort algorithm tailored for linked lists. The overall steps are:

  1. Use the slow and fast pointers to find the middle of the list and split it into two halves.
  2. Recursively sort the two halves.
  3. Merge the two sorted halves by comparing node values.
  4. Ensure that during merging, pointers are adjusted properly to build the sorted list.

For an O(1) space solution, an iterative bottom-up merge sort can be implemented. However, the recursive merge sort is easier to understand and implement, though it uses O(log n) space on the call stack.

Code Solutions

# 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: ListNode) -> ListNode:
        # Base case: if list is empty or contains a single element.
        if not head or not head.next:
            return head
        
        # Function to split the list into two halves
        def getMid(head):
            slow, fast = head, head.next
            # Move fast twice as fast as slow to locate middle
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        
        # Split the linked list into two halves
        mid = getMid(head)
        right_head = mid.next
        mid.next = None  # cut the list into two parts
        
        # Recursive calls to sort each half
        left = self.sortList(head)
        right = self.sortList(right_head)
        
        # Merge two sorted lists
        return merge(left, right)
    
def merge(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    # Merge the lists by comparing nodes
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    # Append the remaining nodes
    tail.next = l1 if l1 else l2
    return dummy.next
← Back to All Questions