algoadvance

Leetcode 148. Sort List

Problem Statement

You are given the head of a linked list. Sort the list in ascending order and return the sorted list.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

Follow up: Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?

Clarifying Questions

  1. Q: Can the linked list contain duplicate values?
    • A: Yes, the list can contain duplicate values.
  2. Q: Should the sorting be in-place (modifying the original linked list) or can we use extra space for a new list?
    • A: The problem is best solved in-place to adhere to space constraints, especially the follow-up that mentions O(1) auxiliary space.
  3. Q: Is the input provided as a ListNode defined class?
    • A: Yes, you should assume that the input linked list is provided as a ListNode defined in common linked list problems.

Strategy

To achieve O(n log n) time complexity and O(1) space complexity, we can use a Merge Sort algorithm applied to the linked list:

  1. Split the list: Split the list into two halves using the slow and fast pointer technique.

  2. Sort each half: Recursively sort each half.

  3. Merge the sorted halves: Merge the two sorted halves.

Code

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // Base case for the recursion
        }
        
        // Step 1: Split the list into halves
        ListNode mid = getMid(head);
        ListNode left = head;
        ListNode right = mid.next;
        mid.next = null; // Break the link

        // Step 2: Sort each half
        left = sortList(left);
        right = sortList(right);

        // Step 3: Merge the sorted halves
        return merge(left, right);
    }
    
    private ListNode getMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        if (l1 != null) {
            current.next = l1;
        } else if (l2 != null) {
            current.next = l2;
        }
        
        return dummy.next;
    }
}

Time Complexity

  1. Splitting: Each split operation takes O(log n).
  2. Merging: Each merge process takes O(n).

Therefore, combining both operations, the overall time complexity is O(n log n).

Space Complexity

Given the constraints of the problem and our approach:

However, the overall auxiliary space is considered to be O(1) as the primary additional space used here is from the recursion stack, which is usually not counted in auxiliary space considerations.

Thus, the solution satisfies the problem’s constraints on both time and space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI