148. Sort List

Description

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

The input is the head of a singly linked list. The list can have up to 10^5 nodes, and each node contains an integer value. The goal is to sort the linked list in ascending order.

Intuition

The problem of sorting a linked list can be approached in multiple ways, but a simple and intuitive method is to leverage the power of sorting algorithms available in standard libraries. By extracting the values from the linked list into an array, sorting the array, and then reconstructing the linked list, we can achieve the desired result in a straightforward manner.

Approach

1. Base Case Handling: - If the list is empty (head is None) or contains only one node (head.next is None), return the head as it is already sorted.
2. Extract Elements: - Traverse the linked list and extract all node values into a Python list (array).
3. Sort Elements: - Use the built-in sort method to sort the elements in ascending order.
4. Reconstruct Linked List: - Create a new sorted linked list using the sorted elements. - Initialize the new list with the first element. - Iterate through the sorted elements and create new ListNode objects, linking them together.
5. Return the Head of the New Sorted List: - Return the head of the newly constructed sorted linked list.

Complexity

Time Complexity:

O(n log n)

• Extracting the elements takes O(n).
• Sorting the elements takes O(n log n) using a comparison-based sort.
• Reconstructing the sorted linked list takes O(n).
• The overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity:

O(n)

• Additional space is used to store the elements in a list before sorting, which requires O(n) space.
• The recursion stack space for the sorting algorithm is O(log n), but the dominant space usage is the list of elements.

Code

C++

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        if (head->next == nullptr) {
            return head;
        }

        // Extract the elements from the linked list
        std::vector elements;
        ListNode* current = head;
        while (current != nullptr) {
            elements.push_back(current->val);
            current = current->next;
        }

        // Sort the elements
        std::sort(elements.begin(), elements.end());

        // Create a new sorted linked list
        ListNode* result = new ListNode(elements[0]);
        ListNode* resultPointer = result;
        for (size_t i = 1; i < elements.size(); ++i) {
            resultPointer->next = new ListNode(elements[i]);
            resultPointer = resultPointer->next;
        }

        return result;
    }
};

Python

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # Extract the elements from the linked list
        elements = []
        current = head
        while current:
            elements.append(current.val)
            current = current.next

        # Sort the elements
        elements.sort()

        # Create a new sorted linked list
        sorted_head = ListNode(elements[0])
        current = sorted_head
        for val in elements[1:]:
            current.next = new_node = ListNode(val)
            current = new_node

        return sorted_head

Java

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // Extract the elements from the linked list
        List elements = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            elements.add(current.val);
            current = current.next;
        }

        // Sort the elements
        Collections.sort(elements);

        // Create a new sorted linked list
        ListNode result = new ListNode(elements.get(0));
        ListNode resultPointer = result;
        for (int i = 1; i < elements.size(); i++) {
            resultPointer.next = new ListNode(elements.get(i));
            resultPointer = resultPointer.next;
        }

        return result;
    }
}

JavaScript

var sortList = function(head) {
    // No need to BFS, let's simpy iterate
    if (head === null){
        return null;
    }
    if (head.next === null){
        return head;
    }
    let elements = []

    while (head != null){
        elements.push(head.val);
        head = head.next;
    }
    elements.sort(function (a,b){return a-b});

    let result = new ListNode(elements.shift());
    let resultPointer = result;

    while (elements.length){
        resultPointer.next = new ListNode(elements.shift())
        resultPointer = resultPointer.next;
    }
    return result;
};