### 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

In this problem, we are given a singly linked list. We have to sort this list using bubble sort.

**Note:** The bubble sort will be applied on nodes instead of values i.e., We have to swap the nodes instead of values.

### Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples by referring the best websites to learn coding.

Suppose the given list is 5 → 1 → 4 → 2 → 8.

- According to the problem statement, we have to sort the given list using bubble sort.
- What do we usually do? We usually swap the node data. But here, we have to swap the nodes and not their data.
- In the first step, suppose we have to swap 5 and 1. So, we will swap the nodes and not their data. So, the linked list after the first step will be 1 → 5 → 4 → 2 → 8. In this way, swapping will happen, and our final sorted linked list will be 1 → 2 → 4 → 5 → 8

**Input:**

**Output:**

**Explanation:** As we can see, the given singly linked list has been sorted.

This question is not a very complex one. We have to apply a normal bubble sort on the list. The only difference is that instead of swapping the data of adjacent nodes, we will swap the nodes. Let us have a glance at the approach.

### Approach and Algorithm

### Swap() function

In the swap() function, we will see how we can swap two adjacent nodes.

- Let the two adjacent nodes be
**p1**and**p2**. - Now we will create 2 pointers
**ptr1**and**ptr2**, and will make**ptr1**point to**p1**and**ptr2**point to**p2**. - Next, we will create a pointer
**temp**, and will make it point to the next of**ptr2**. - We will make the next of
**ptr2**point to**ptr1**and next of**ptr1**point to**temp**. - In this way, following the above steps, the two adjacent nodes
**p1**and**p2**will get swapped.

### Dry Run (Swap() function)

### BubbleSort()

In this method, we will see how to perform Bubble Sort on the linked list.

- First, we need the count of the number of nodes in the list. The count can be found with a single list traversal.
- Now, the first loop is going to run from
**0**to**count-1**. - Inside the first loop, we will create a node pointer
**h**that will point to the head and a variable**swapped**, initializing it with**0**. - The nested loop will run from
**0**to**count-i-1**. - Inside the nested loop, we will check if the adjacent elements are following ascending order or not.
- If any pair of adjacent nodes are not following the ascending order, we will swap the nodes and the value of swapped will become 1.

- After the above, if condition, we will increment the
**h**. - Now, after the inner loop, if the value of the variable swapped remains 0, it means that the list is sorted, and we will break the loop. Otherwise we will continue with the loop.

### Dry Run (Bubble sort)

### Code Implementation

#includeusing namespace std; struct Node { int data; struct Node* next; } Node; struct Node* swap(struct Node* ptr1, struct Node* ptr2) { struct Node* tmp = ptr2->next; ptr2->next = ptr1; ptr1->next = tmp; return ptr2; } int bubbleSort(struct Node** head, int count) { struct Node** h; int i, j, swapped; for (i = 0; i < count; i++) { h = head; swapped = 0; for (j = 0; j < count - i -1; j++) { struct Node* p1 = *h; struct Node* p2 = p1->next; if (p1->data > p2->data) { *h = swap(p1, p2); swapped = 1; } h = &(*h)->next; } if (swapped == 0) break; } } void printList(struct Node* n) { while (n != NULL) { cout << n->data << " -> "; n = n->next; } cout << endl; } void insertAtTheBegin(struct Node** start_ref, int data) { struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node)); ptr1->data = data; ptr1->next = *start_ref; *start_ref = ptr1; } int main() { int arr[] = { 8, 2, 4, 1, 5 }; int list_size, i; struct Node* start = NULL; list_size = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < list_size; i++) insertAtTheBegin(&start, arr[i]); cout <<"Linked list before sorting\n"; printList(start); bubbleSort(&start, list_size); cout <<"Linked list after sorting\n"; printList(start); return 0; }

### Output

Linked list before sorting

5 -> 1 -> 4 -> 2 -> 8 ->

Linked list after sorting

1 -> 2 -> 4 -> 5 -> 8 ->

**Time Complexity:** O(n^{2}), as a nested traversal, is needed.

So, in this article, we have tried to explain how to sort a linked list using bubble sort. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.