### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

According to the problem statement, we are given a singly linked list, and we need to sort this singly linked list using merge sort.

### Merge Sort

Merge sort is a divide and conquer algorithm.

- It is a recursive algorithm.
- In merge sort, we have to divide the container (container can be an array, list etc.) into two halves, then we will call merge sort recursively on the two halves.
- These two merge sort call return sorted container, and we then merge these sorted container in such a way that the whole container remains sorted.
- Have a look at the below image to see in a nutshell how merge sort works.

Now, we have a brief understanding of the merge sort algorithm. Letâ€™s learn how to apply merge sort on a singly linked list.

In the case of a linked list, we will recursively divide the list into two sub-lists at each step till list size is reduced to one and while backtracking from the recursive call, we have two sorted lists, which will be merged together into a single list by merge operation in linear time.

Now we will look at the approach and algorithm, to know how to apply merge sort on a singly linked list.

### Approach and Algorithm (Merge Sort)

1) If the **head** of the linked list is NULL or **(headâ†’ next == NULL)**, it shows that our linked list is of size 1 or 0 and a linked list of size zero or one is already sorted. So, Donâ€™t do anything, just return **head**.

2) If the linked list is of **size > 1** then first find the **middle** of the linked list.

- For finding middle node, use
**slow and fast pointer method**. - In this method, we take two pointers
**slow**and**fast**and initialize them with**head**. - Then we move the
**slow pointer**by one node and**fast pointer**by 2 nodes until fast pointer reaches the tail of the list. - And when the
**fast pointer**reaches the**tail**, the**slow pointer**will be at the**middle**of the linked list. - The only reason why
**slow pointer**will be at the**middle**of the list, when**fast**reaches**tail**is because the**slow pointer is moving with half the speed of fast pointer**and when the fast pointer has traversed the complete list till then the slow pointer will have only traversed half the list, so thatâ€™s why slow pointer will be at the middle of the list.

3) Now, store**slow â†’ next**in a pointer named**afterMiddle**and assign**slow â†’ next = NULL**.

4) Recursively call**mergeSort()**on both**left and right sub-linked list**and store the new head of the left and right linked list in pointer variable**part1**and**part2**.

5) When the recursive call on the left and right sub-list returns, merge the two linked lists returned by recursive calls (remember that the recursive call will return the sorted lists).

6) Return the final head of the merged linkedlist.

#### Merging two sorted linked list Algorithm:

When the two recursive call will return the two sorted list, then we will merge those sorted list into a single list using these below steps.

1) Initialize two pointer variables named **curr1** and **curr2** with left sorted sub-list and right sorted sub-list.

2) Initialize two pointer variable named **si** and **ei** with NULL; these two pointer variables are the **head** and **tail** of the final sorted linked list.

3) If the data of **curr1** is less than the data of **curr2**, then, store **curr1** in next of **ei** & move **curr1** to the next of **curr1**.

4) Else, if the data of **curr2** is less than the data of **curr1**, then store **curr2** in next of **ei** & move **curr2** to the next of **curr2**.

5) Repeat steps 3 and 4 until either of the **curr1** or **curr2** is not equal to NULL.

6) Now add any remaining nodes of the first or the second linked list to the merged linked list.

7) Return head of merged sorted linked list containing all the nodes of the two sorted sub-lists.

### Dry Run

### Code Implementation

#includeusing namespace std; /* structure of node */ class Node{ public: int data; Node* next; Node(int data){ this->data = data; this->next = NULL; } }; /* print linked list */ void printList(Node* node){ while (node != NULL) { cout< data<<" "; node = node->next; } printf("\n"); } /* find and return middle node of the linked list*/ Node* middle(Node* head, Node* tail) { Node* slow = head; Node* fast = head; while(fast!=tail && fast->next!=tail){ slow = slow->next; fast = fast->next->next; } Node* afterMiddle = slow->next; slow->next = NULL; return afterMiddle; } /* merge sort*/ Node* mergeSort(Node* head){ if(head == NULL || head->next == NULL){ return head; } Node* tail = head; while(tail->next){ tail = tail->next; } Node* afterMiddle = middle(head, tail); Node* part1 = mergeSort(head); Node* part2 = mergeSort(afterMiddle); Node *curr1 = part1, *curr2 = part2; Node *si = NULL, *ei = NULL; while(curr1 && curr2){ if(curr1->data <= curr2->data){ if(si == NULL){ si = curr1; ei = curr1; }else{ ei->next = curr1; ei = curr1; } curr1 = curr1->next; }else{ if(si == NULL){ si = curr2; ei = curr2; }else{ ei->next = curr2; ei = curr2; } curr2 = curr2->next; } } while(curr1){ ei->next = curr1; ei = curr1; curr1 = curr1->next; } while(curr2){ ei->next = curr2; ei = curr2; curr2 = curr2->next; } return si; } int main(){ Node n1 = Node(8); Node n2 = Node(9); Node n3 = Node(5); Node n4 = Node(3); Node n5 = Node(2); Node n6 = Node(7); n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = &n5; n5.next = &n6; Node* head = &n1; cout << "Linked List before sorting \n"; printList(head); head = mergeSort(head); cout << "Linked List after sorting \n"; printList(head); }

#### Output

Linked List before sorting

8 9 5 3 2 7

Linked List after sorting

2 3 5 7 8 9

**Time Complexity:** O(n*log n)

So, In this blog, we have learned How to merge sort on a Singly Linked List. This is an important question when it comes to coding interviews. If you want to practice more questions on linked lists feel free to solve them at Prepbytes (Linked Lists).