To sort a linked list, we can use various sorting algorithms such as merge sort, bubble sort, or insertion sort. Here, we will implement merge sort to sort a linked list.
The merge sort algorithm for sorting a linked list can be divided into three steps:
- Divide: Divide the linked list into two halves using the fast and slow pointer technique.
- Conquer: Recursively sort the two halves of the linked list using merge sort.
- Merge: Merge the two sorted halves of the linked list into a single sorted list using a merge function.
Let's take a look at an example implementation of merge sort for a linked list in C++:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4// Node definition
5struct Node {
6 int data;
7 Node* next;
8 Node(int d) : data(d), next(nullptr) {}
9};
10
11// Function to insert a new node at the beginning of the list
12void insertAtBeginning(Node** head, int value) {
13 Node* newNode = new Node(value);
14 newNode->next = *head;
15 *head = newNode;
16}
17
18// Function to print the linked list
19void printList(Node* head) {
20 Node* temp = head;
21 while (temp != nullptr) {
22 cout << temp->data << " ";
23 temp = temp->next;
24 }
25}
26
27int main() {
28 // Create a linked list
29 Node* head = nullptr;
30 insertAtBeginning(&head, 5);
31 insertAtBeginning(&head, 10);
32 insertAtBeginning(&head, 3);
33 insertAtBeginning(&head, 8);
34
35 // Print the linked list
36 cout << "Linked List: ";
37 printList(head);
38
39 return 0;
40}xxxxxxxxxx40
}using namespace std;// Node definitionstruct Node { int data; Node* next; Node(int d) : data(d), next(nullptr) {}};// Function to insert a new node at the beginning of the listvoid insertAtBeginning(Node** head, int value) { Node* newNode = new Node(value); newNode->next = *head; *head = newNode;}// Function to print the linked listvoid printList(Node* head) { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; }}int main() { // Create a linked list Node* head = nullptr;OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
