C++ Online Compiler
Example: Linked List Merge Sort in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Linked List Merge Sort #include <iostream> #include <cstddef> // For NULL using namespace std; // Node structure for the linked list struct Node { int data; Node* next; Node(int val) : data(val), next(NULL) {} }; // Function to merge two sorted linked lists Node* mergeTwoSortedLists(Node* list1, Node* list2) { // Base cases if (list1 == NULL) return list2; if (list2 == NULL) return list1; Node* result = NULL; // Pick either list1 or list2, and recurse if (list1->data <= list2->data) { result = list1; result->next = mergeTwoSortedLists(list1->next, list2); } else { result = list2; result->next = mergeTwoSortedLists(list1, list2->next); } return result; } // Function to find the middle of a linked list Node* getMiddle(Node* head) { if (head == NULL) return head; Node* slow = head; Node* fast = head->next; // Start fast one ahead while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } // Function to sort a linked list using Merge Sort Node* mergeSort(Node* head) { // Base case: if head is NULL or has only one node if (head == NULL || head->next == NULL) { return head; } // Step 1: Find the middle of the list to divide it into two halves Node* middle = getMiddle(head); Node* nextOfMiddle = middle->next; // Store the head of the second half // Step 2: Break the link to split the list into two halves middle->next = NULL; // Step 3: Recursively sort the two halves Node* left = mergeSort(head); Node* right = mergeSort(nextOfMiddle); // Step 4: Merge the sorted halves Node* sortedList = mergeTwoSortedLists(left, right); return sortedList; } // Function to print the linked list void printList(Node* head) { Node* temp = head; while (temp != NULL) { cout << temp->data << " -> "; temp = temp->next; } cout << "NULL" << endl; } int main() { // Step 1: Create an unsorted linked list Node* head = new Node(5); head->next = new Node(2); head->next->next = new Node(8); head->next->next->next = new Node(1); head->next->next->next->next = new Node(4); head->next->next->next->next->next = new Node(9); // Added one more for odd length cout << "Original list: "; printList(head); // Step 2: Sort the linked list using Merge Sort head = mergeSort(head); cout << "Sorted list (Merge Sort): "; printList(head); // Step 3: Clean up memory while (head != NULL) { Node* temp = head; head = head->next; delete temp; } return 0; }
Output
Clear
ADVERTISEMENTS