Sort linked list in C
IntroductionThe 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. Show Problem StatementIn 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 UnderstandingLets 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.
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 AlgorithmSwap() functionIn the swap() function, we will see how we can swap two adjacent nodes.
Dry Run (Swap() function)BubbleSort()In this method, we will see how to perform Bubble Sort on the linked list.
Dry Run (Bubble sort)Code Implementation
#include
using 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;
}
OutputLinked list before sorting Time Complexity: O(n2), as a nested traversal, is needed. Let us check your understanding!!Think before you answer What is the Space complexity for this algorithm? O(n) O(1) O(logn) None of these 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. |