Sort a linked list

Sorting a linked list is a common problem in computer science and programming. Linked lists are dynamic data structures used to store and manage collections of data. Sorting them efficiently is essential for various applications. In this article, we will explore the problem of sorting a linked list, understand how it works, delve into the algorithm and solution, provide C++ code examples, and analyze the time and space complexity of the solution.

How Does It Work?

Sorting a linked list involves arranging its elements in a specific order, such as ascending or descending. Unlike arrays, linked lists do not provide direct access to elements by index, which makes sorting a bit more challenging. To achieve this, we typically use one of the popular sorting algorithms, such as Merge Sort or Quick Sort, tailored for linked lists.

Merge Sort algorithm as presented in the provided code will work correctly for linked lists that contain duplicate values. The algorithm is designed to handle duplicates effectively.

Algorithm / Solution

We will discuss the Merge Sort algorithm for sorting a linked list because of its efficiency and ease of implementation for this data structure. Here's how it works:

1. Divide the linked list into two halves by finding the middle point. This can be done using the slow and fast pointer technique.
2. Recursively sort the two halves separately until they are sorted individually.
3. Merge the two sorted halves back together to create a single sorted linked list.
4. Return the sorted linked list.

Let's take an example of a linked list with duplicate values and use the provided code to sort it while preserving duplicates. Consider the linked list: 4 -> 2 -> 1 -> 3 -> 2 -> 4

C++ Code

#include <iostream>

// Definition for singly-linked list
struct ListNode {
   int val;
   ListNode* next;
   ListNode(int x) : val(x), next(nullptr) {}
};

// Merge two sorted linked lists
ListNode* merge(ListNode* left, ListNode* right) {
   if (!left) return right;
   if (!right) return left;

   if (left->val < right->val) {
       left->next = merge(left->next, right);
       return left;
   } else {
       right->next = merge(left, right->next);
       return right;
   }
}

// Merge Sort function for linked lists
ListNode* mergeSort(ListNode* head) {
   if (!head || !head->next) return head;

   // Find the middle of the linked list
   ListNode* slow = head;
   ListNode* fast = head->next;

   while (fast && fast->next) {
       slow = slow->next;
       fast = fast->next->next;
   }

   ListNode* left = head;
   ListNode* right = slow->next;
   slow->next = nullptr; // Split the list into two halves

   left = mergeSort(left);
   right = mergeSort(right);

   return merge(left, right);
}

int main() {
   // Example linked list: 4 -> 2 -> 1 -> 3 -> 2 -> 4
   ListNode* head = new ListNode(4);
   head->next = new ListNode(2);
   head->next->next = new ListNode(1);
   head->next->next->next = new ListNode(3);
   head->next->next->next->next = new ListNode(2);
   head->next->next->next->next->next = new ListNode(4);

   std::cout << "Original linked list: ";
   ListNode* current = head;
   while (current) {
       std::cout << current->val << " ";
       current = current->next;
   }
   std::cout << std::endl;

   // Sort the linked list using Merge Sort
   head = mergeSort(head);

   std::cout << "Sorted linked list: ";
   current = head;
   while (current) {
       std::cout << current->val << " ";
       current = current->next;
   }
   std::cout << std::endl;

   return 0;
}

Output

Original linked list: 4 2 1 3 2 4

Sorted linked list: 1 2 2 3 4 4

Time Complexity

The time complexity of Merge Sort for a linked list is O(n log n), where n is the number of elements in the list. This is because we divide the list into halves and merge them repeatedly.

Space Complexity

The space complexity is O(log n) due to the recursive nature of the algorithm. It requires additional space on the call stack for function calls during the recursion.

In the provided code, we start with an unsorted linked list (4 -> 2 -> 1 -> 3 -> 2 -> 4) and use Merge Sort to sort it. The output shows the original linked list and the sorted linked list.