algoadvance

The problem is to sort a linked list in O(n log n) time using constant space complexity. You are given the head of the linked list, and you need to return the head of the sorted linked list.

Clarifying Questions

1. What type of data does each node contain? Each node contains an integer value.

2. Are there any constraints on the values of the nodes (positive, negative, large numbers)? No, the nodes can contain any integer value.

3. Is the input list always valid (i.e., no cycles)? Yes, the problem statement assumes a well-formed linked list with no cycles.

4. What should be returned if the list is empty? If the list is empty (head is None), return None.

Strategy

• We need to sort the linked list in O(n log n) time and use constant space. The most suitable sorting algorithm for this scenario that satisfies both constraints is Merge Sort.
• The method involves:
  1. Splitting the list: We’ll use the fast and slow pointer technique to find the middle of the list and split it into two halves.
  2. Sorting each half recursively: We’ll apply the Merge Sort recursively to sort each half.
  3. Merging the sorted halves: We’ll merge the two sorted halves into a single sorted list.

Code

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
    
    # Split the list into two halves
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    mid = slow.next
    slow.next = None
    
    # Recursively split & sort
    left = sortList(head)
    right = sortList(mid)
    
    # Merge sorted halves
    return merge(left, right)

def merge(left: ListNode, right: ListNode) -> ListNode:
    dummy = ListNode()
    tail = dummy
    
    while left and right:
        if left.val < right.val:
            tail.next = left
            left = left.next
        else:
            tail.next = right
            right = right.next
        tail = tail.next
    
    if left:
        tail.next = left
    if right:
        tail.next = right
    
    return dummy.next

Time Complexity

• Splitting the list: Each split operation takes O(n) because we traverse the entire list once with the fast and slow pointers.
• Sorting each half: Each recursive call sorts half of the list, resulting in a depth of log(n) (since we’re dividing the list by 2 at each step).
• Merging sorted halves: Each merge operation takes O(n) since it goes through the entire length of the list.

Combining these, the overall time complexity is O(n log n). The space complexity is O(1), assuming that the recursion stack space does not count as extra space, which aligns with the problem’s constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?