Problem Statement

Given the head of a singly linked list. Sort the values of the linked list in non-decreasing order and return the head of the modified linked list.

Examples

Example 1:

Input: 5->6->1->2->1
Output: 1->1->2->5->6

Example 2:

Input: 6->5->1->2->4
Output: 1->2->4->5->6

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A straightforward approach to sorting a linked list involves converting the linked list into an array. Once converted, the array can be sorted using any standard sorting algorithm. After sorting, a new linked list can be created using the sorted values from the array.

Approach:

1. Create an empty array to store the node values.
2. Traverse the linked list using a temporary pointer starting at the head, pushing each node's value into the array, and moving the pointer to the next node.
3. Sort the array containing the node values in ascending order.
4. Convert the sorted array back into a linked list by reassigning the values from the sorted array to the nodes, overwriting the values sequentially according to the order in the array.

Code:

#include <bits/stdc++.h>

using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(NULL) {}
    ListNode(int data1) : val(data1), next(NULL) {}
    ListNode(int data1, ListNode *next1) : val(data1), next(next1) {}
};

class Solution {
public:
    // Function to sort Linked List
    ListNode* sortList(ListNode* head) {
        // Vector to store node values
        vector<int> arr;

        /*Temporary pointer to
        traverse the linked list*/
        ListNode* temp = head;

       /* Traverse the linked list and
       store node values in the vector*/
        while(temp != NULL) {
            arr.push_back(temp->val);
            temp = temp->next;
        }

        // Sort array containing node values
        sort(arr.begin(), arr.end());

        // Reassign sorted values to linked list nodes
        temp = head;
        for(int i = 0; i < arr.size(); i++) {
            // Update the node's data
            temp->val = arr[i];
            // Move to the next node
            temp = temp->next;
        }

        // Return the head
        return head;
    }
};

// Function to print the linked list
void printLinkedList(ListNode* head) {
    ListNode* temp = head;
    while (temp != nullptr) {
        // Print the data of the current node
        cout << temp->val << " ";
        // Move to the next node
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // Linked List: 3 2 5 4 1
    ListNode* head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(5);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(1);

    cout << "Original Linked List: ";
    printLinkedList(head);

    Solution solution;
    // Sort the linked list
    head = solution.sortList(head);

    cout << "Sorted Linked List: ";
    printLinkedList(head);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) + O(N log N) + O(N), where N represents the number of nodes in the linked list.
  • O(N): Time taken to traverse the linked list and store its data values in an array.
  • O(N log N): Time taken to sort the array of node values.
  • O(N): Time taken to traverse the sorted array and reassign values back to the linked list.
• Space Complexity: O(N) because we need to store values of nodes of the linked lists in the array of size N where N is the length of the linked list.

2️⃣ Optimal Approach

Intuition:

Instead of using an external array to store node values, we can utilize an in-place sorting algorithm such as Merge Sort or Quick Sort, which can be adapted for linked lists. This approach avoids using additional space.

Merge Sort employs the divide and conquer strategy:-

• Divides the linked list into smaller parts until they become trivial to sort (single node or empty list).
• Merges and sorts the divided parts while combining them back together.

Approach:

• Base Case: If the linked list contains zero or one element, it is already sorted. Return the head node.
• Split the List: Find the middle of the linked list using a slow and a fast pointer. Split the linked list into two halves at the middle node. The two halves will be left and right.
• Recursion: Recursively apply merge sort to both halves obtained in the previous step. This step continues dividing the linked list until there's only one node in each half.
• Merge Sorted Lists: Merge the sorted halves obtained from the recursive calls into a single sorted linked list. Compare the nodes from both halves and rearrange them to form a single sorted list. Update the head pointer to the beginning of the newly sorted list.
• Return: Once the merging is complete, return the head of the sorted linked list.

Template for Merge Sort:

ms(arr, low, high):
    if low == high:
        return

    mid = (low + high) / 2

    ms(arr, low, mid)      // Sort the left half
    ms(arr, mid + 1, high) // Sort the right half

    merge(arr, low, mid, high) // Merge the two halves

Dry Run:

Code:

/*
Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};
*/

class Solution {
public:

    // Function to find the middle of the linked list
    ListNode* findMiddle(ListNode* head) {
        ListNode* slow = head;        // Slow pointer (moves one step at a time)
        ListNode* fast = head->next; // Fast pointer (moves two steps at a time)

        // Move pointers until fast pointer reaches the end of the list
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;        // Move slow pointer one step
            fast = fast->next->next; // Move fast pointer two steps
        }
        return slow; // Slow pointer is now at the middle of the list
    }

    // Function to merge two sorted linked lists
    ListNode* merge(ListNode* leftHalf, ListNode* rightHalf) {
        // Create a dummy node to simplify merging
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy; // Pointer to track the current position

        // Merge the two halves while both have elements
        while(leftHalf != nullptr && rightHalf != nullptr) {
            if(leftHalf->val <= rightHalf->val) {
                // If the current element in the left half is smaller
                curr->next = leftHalf; // Add left node to merged list
                leftHalf = leftHalf->next; // Move to the next node in left half
            } else {
                // If the current element in the right half is smaller
                curr->next = rightHalf; // Add right node to merged list
                rightHalf = rightHalf->next; // Move to the next node in right half
            }
            curr = curr->next; // Move to the next node in the merged list
        }

        // Attach any remaining nodes in the left half
        if (leftHalf != nullptr) {
            curr->next = leftHalf;
        } 
        // Attach any remaining nodes in the right half
        else {
            curr->next = rightHalf;
        }

        return dummy->next; // Return the head of the merged list
    }

    // Function to sort the linked list using merge sort
    ListNode* sortList(ListNode* head) {
        // Base case: If the list is empty or contains a single node, it's already sorted
        if(head == nullptr || head->next == nullptr) {
            return head;
        }

        // Find the middle of the list
        ListNode* middle = findMiddle(head);

        // Split the list into two halves
        ListNode* leftHalf = head;         // Left half starts from the head
        ListNode* rightHalf = middle->next; // Right half starts from the node after the middle
        middle->next = nullptr;            // Separate the two halves

        // Recursively sort the left half and right half
        ListNode* sortedLeftHalf = sortList(leftHalf);
        ListNode* sortedRightHalf = sortList(rightHalf);

        // Merge the two sorted halves and return the result
        return merge(sortedLeftHalf, sortedRightHalf);
    }
};

Complexity Analysis:

• Time Complexity: O(N log N) where N is the number of nodes in the linked list. Finding the middle node of the linked list requires traversing it linearly taking O(N) time complexity and to reach the individual nodes of the list, it has to be split log N times (continuously halve the list until we have individual elements).
• Space Complexity: O(1) as no additional data structures or space is allocated for storage during the merging process. However, space proportional to O(log N) stack space is required for the recursive calls. The maximum recursion depth of log N height is occupied on the call stack.