A linked list is a sequential collection of data elements connected via links. The data element of a linked list is known as a node which contains two parts namely- the data part and the pointer. For sorting a linked list, we can use the insertion sort-based algorithm as well as the merge sort algorithm. The insertion sort-based algorithm uses nested loops so its time complexity comes out to be higher than the merge sort algorithm. The merge sort algorithm simply divides the list into smaller halves and then sorts the smaller ones. Finally, the smaller ones are merged in a sorted fashion to get the complete sorted list.
Takeaways
- Time complexity for sorting linked list using merge-sort: O(n∗logn)
What is Linked List?
As the name suggests, a linked list is a sequential collection of data elements connected via links. The data element of a linked list is known as a node which contains two parts namely- the data part and the pointer. The data part contains the actual data and the pointer part contains a pointer that points to the next element of the linked list.
There are various types of linked lists:
- Singly-linked list.
- Doubly linked list.
- Circular linked list.
- Doubly circular linked list.
- Skip linked list, etc.
To learn more about Linked Lists, refer here.
Concept of Sorting Linked List
For sorting a linked list, we can use an insertion sort kind of technique. We can use two points (let’s say current and nextNode are those two pointers). At first, the current pointer will be to the head of the linked list and the nextNode pointer will point to the second node of the linked list (or the next node to the current node).
Now, we would traverse the entire linked list (until the current node is not equal to null), and in each step, we will check if the current node’s data is greater than a node’s data. In case it is larger, we will swap the data between them.
In each iteration, we will select one current node and place the currently selected node at its correct sorted position in the given linked list.
Example:
Refer to the algorithm and implementation of how we can sort a linked list for better understanding.
Algorithm to Sort Linked List
We need to call the sortLinkedList() function. Inside the sortLinkedList() function, we need to perform certain steps:
- We will first create two nodes namely current and nextNode .
- The current node will be pointing at the head of the linked list.
- The nextNode will be pointing to the second node of the linked list.
- In the next step, we need to compare all the nodes of the linked list with the current node. If the data of the current node is greater, then we need to swap the data of the current node and the the currently processing node.
- After the swapping, the current node will point to the next node to the current node (i.e. current->next).
- We will continue the entire above steps until the linked list is sorted.
Let us now try to code out the algorithm.
Program to Sort Linked List
Let us now look at the implementation of the algorithm to sort a linked list for more clarity.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
// creating a linked list node.
class Node {
public:
int data;
Node *next;
};
// a helper function that will set the currentNode at its correct position.
void sortListHelper(Node **head, Node *newNode) {
Node temp;
Node *current = &temp;
temp.next = *head;
// checking the current node with each node of the linked list if it is smaller then we are swapping.
while (current->next != NULL && current->next->data < newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
*head = temp.next;
}
// a function that will sort the linked list.
void sortLinkedList(Node **head) {
// a list to store the current result
Node *answerList = NULL;
/*
the current node will be pointing at the head of the linked list and the nextNode will be pointing to the second node of the linked list.
*/
Node *current = *head;
Node *nextNode;
while (current != NULL) {
/*
setting the nextNode pointer to the next node and calling the helper function that will set the current node at its correct position.
*/
nextNode = current->next;
sortListHelper(&answerList, current);
current = nextNode;
}
// finally making the head node point to the resultant sorted linked list.
*head = answerList;
}
// a function to traverse and print the linked list.
void printList(Node *head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
/*
insertNode function will create a new node and insert the newly created node at the last.
*/
void insertNode(Node **head, int newData) {
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
int main() {
// an empty linked list
Node *l = NULL;
insertNode(&l, 12);
insertNode(&l, 2);
insertNode(&l, 1);
insertNode(&l, 15);
// printing the linked list before sorting
cout << "Original Linked list: " << endl;
printList(l);
// sorting the linked list.
sortLinkedList(&l);
// printing the linked list after sorting
cout << "\nSorted Linked list: " << endl;
printList(l);
return 0;
}
Java Code:
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data, Node next) {
this.data = data;
this.next = next;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
// a function to traverse and print the linked list.
public static void printList(Node head) {
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.data + " ");
ptr = ptr.next;
}
}
// a helper function that will set the currentNode at its correct position.
public static Node sortListHelper(Node head, Node newNode) {
Node temp = new Node();
Node current = temp;
temp.next = head;
// checking the current node with each node of the linked list if it is smaller then we are swapping.
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return temp.next;
}
// a function that will sort the linked list.
public static Node sortLinkedList(Node head) {
// a list to store the current result
Node result = null;
Node current = head;
Node nextNode;
/*
the current node will be pointing at the head of the linked list and the nextNode will be pointing to the second node of the linked list.
*/
while (current != null) {
/*
setting the nextNode pointer to the next node and calling the helper function that will set the current node at its correct position.
*/
nextNode = current.next;
result = sortListHelper(result, current);
current = nextNode;
}
/*
finally returning the resultant sorted linked list making it the head node of the sorted linked list.
*/
return result;
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 12, 2, 1, 15 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i], head);
}
// printing the linked list before sorting
System.out.println("Original Linked list: ");
printList(head);
// sorting the linked list.
head = sortLinkedList(head);
// print linked list
System.out.println("\nSorted Linked list: ");
printList(head);
}
}
Python Code:
# creating a linked list node.
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# a function to traverse and print the linked list.
def printList(head):
temp = head
while temp:
print(temp.data, end=" ")
temp = temp.next
# a helper function that will set the currentNode at its correct position.
def sortLinkedListHelper(head, newNode):
temp = Node()
current = temp
temp.next = head
# checking the current node with each node of the linked list if it is smaller then, we are swapping.
while current.next and current.next.data < newNode.data:
current = current.next
newNode.next = current.next
current.next = newNode
return temp.next
# a function that will sort the linked list.
def sortLinkedList(head):
# a list to store the current result
answerList = None
current = head
# current node will be pointing at the head of the linked list
while current:
"""
setting the nextNode pointer to the next node and calling the helper function that will set the current node at its correct position.
"""
nextNode = current.next
answerList = sortLinkedListHelper(answerList, current)
current = nextNode
"""
finally returning the resultant sorted linked list making it the head node of the sorted linked list.
"""
return answerList
if __name__ == '__main__':
# a list containing the data of the linked list.
data = [12, 2, 1, 15]
# points to the head node of the linked list
head = None
# constructing the linked list from last to first
for i in reversed(range(len(data))):
head = Node(data[i], head)
# printing the linked list before sorting
print("Original Linked list: ")
printList(head)
# sorting the linked list.
head = sortLinkedList(head)
# print linked list
print("\nSorted Linked list: ")
printList(head)
Output:
Original Linked list:
15 1 2 12
Sorted Linked list:
1 2 12 15
How to Sort a Linked List Using Merge Sort?
We can sort a linked list using the merge sort algorithm as well. Merge sort is one of the divide and conquer techniques as it divides the linked list into halves until the size of the linked list is greater than equal to one.
The idea of divide and conquer is very simple, just divide the input into smaller sub-problems and then find the solution to those smaller problems. Once the smaller problem is solved then the results can be combined to get the solution to a larger problem.
Refer to the diagram of the divide and conquer technique for better understanding.
The idea or merge sort is very simple, we will take an input linked list (let’s say l), and we will divide it into halves until the size of the linked list is greater than equal to one. This step is known as the divide step.
Suppose the input linked list is [1, 5, 4, 9, 10, 6]. Now in each step, we will divide it into halves as sorting the smaller portion is easier than sorting the entire linked list. Refer to the diagram specified below to understand how the division operation is taking place.
Now, in the conquer part, we will sort the smaller halves and then merge the sorted parts to get larger sorted portions. In this way, we will merge smaller sorted links in sorted order.
Refer to the diagram specified below to understand how the conquer operation occurs.
Let us now discuss the step-by-step algorithm.
Algorithm
We need to call the mergeSort() function. Inside the mergeSort() function, we need to perform certain steps:
- First, handle the base case i.e. if the head pointer of the linked list is pointing to null then we cannot perform anything, so return.
- Else, we will divide the linked list into smaller halves.
- Now, we will sort the smaller halves of the linked list.
- Finally, we will merge this sorted linked list and update the head pointer pointing to the head of the merged linked list.
Implementation
Let us now code the above-discussed algorithm for more clarity.
C++ Code:
// C++ code for linked list merged sort
#include <bits/stdc++.h>
using namespace std;
// Link list Node
class Node {
public:
int data;
Node *next;
};
// Merging the sorted linked list.
Node *mergeSortedList(Node *list1, Node *list2) {
// a result pointer that will point the merged list.
Node *result = NULL;
// handling the base cases
if (list1 == NULL)
return (list2);
else if (list2 == NULL)
return (list1);
// recursively merging two sorted lists
if (list1->data <= list2->data) {
result = list1;
result->next = mergeSortedList(list1->next, list2);
}
else {
result = list2;
result->next = mergeSortedList(list1, list2->next);
}
// returning the merged sorted list.
return result;
}
// Splitting the linked list into halves.
void splitListIntoHalves(Node *source, Node **front, Node **back) {
Node *pointer1;
Node *pointer2;
pointer2 = source;
pointer1 = source->next;
// we will use the two pointer technique to get the halves of the original linked list.
while (pointer1 != NULL) {
pointer1 = pointer1->next;
if (pointer1 != NULL) {
pointer2 = pointer2->next;
pointer1 = pointer1->next;
}
}
// pointer2 will point at the mid point.
*front = source;
*back = pointer2->next;
pointer2->next = NULL;
}
// a function that will sort the linked list.
void mergeSort(Node **node) {
Node *head = *node;
Node *pointer1;
Node *pointer2;
// handling the base cases.
if ((head == NULL) || (head->next == NULL))
return;
// Splitting linked list into smaller halves.
splitListIntoHalves(head, &pointer1, &pointer2);
// Recursively sorting the divided linked list.
mergeSort(&pointer1);
mergeSort(&pointer2);
// let the head pointer now point to the sorted linked list.
*node = mergeSortedList(pointer1, pointer2);
}
// a function to traverse and print the linked list.
void printList(Node *head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// insertNode function will create a new node and insert the newly created node at the last.
void insertNode(Node **head, int newData) {
Node *newNode = new Node();
newNode->data = newData;
newNode->next = (*head);
(*head) = newNode;
}
int main() {
// an empty linked list.
Node *l = NULL;
insertNode(&l, 12);
insertNode(&l, 2);
insertNode(&l, 1);
insertNode(&l, 15);
// printing the linked list before sorting.
cout << "Original Linked list: " << endl;
printList(l);
// sorting the linked list.
mergeSort(&l);
// printing the linked list after sorting.
cout << "\nSorted Linked list: " << endl;
printList(l);
return 0;
}
Java Code:
// creating a linked list node.
class Node {
int data;
Node next;
// a non-parameterized constructor.
Node(int data, Node next) {
this.data = data;
this.next = next;
}
// a non-parameterized constructor.
Node() {
}
}
public class Main {
public static void printList(Node head) {
Node pointer = head;
while (pointer != null) {
System.out.print(pointer.data + " ");
pointer = pointer.next;
}
}
// Merging the sorted linked list.
public static Node mergeSortedList(Node list1, Node list2) {
// handling the base cases
if (list1 == null)
return list2;
else if (list2 == null)
return list1;
// a result pointer that will point to the merged list.
Node result;
// recursively merging two sorted lists
if (list1.data <= list2.data) {
result = list1;
result.next = mergeSortedList(list1.next, list2);
} else {
result = list2;
result.next = mergeSortedList(list1, list2.next);
}
// returning the merged sorted list.
return result;
}
// Splitting the linked list into halves.
public static Node[] splitListIntoHalves(Node pointer) {
// handling the base cases.
if (pointer == null || pointer.next == null) {
return new Node[] { pointer, null };
}
Node back = pointer;
Node front = pointer.next;
// we will use the two pointer technique to get the halves of the original
// linked list.
while (front != null) {
front = front.next;
if (front != null) {
back = back.next;
front = front.next;
}
}
/*
the pointer will point at the mid point and (back.next) is the pointer pointing to the second linked list.
*/
Node[] list = new Node[] { pointer, back.next };
back.next = null;
return list;
}
// a function that will sort the linked list.
public static Node mergeSort(Node head) {
// handling the base cases.
if (head == null || head.next == null) {
return head;
}
Node[] list = splitListIntoHalves(head);
// Splitting linked list into smaller halves.
Node firstList = list[0];
Node secondList = list[1];
// Recursively sorting the divided linked list.
firstList = mergeSort(firstList);
secondList = mergeSort(secondList);
// let the head pointer now point to the sorted linked list.
return mergeSortedList(firstList, secondList);
}
public static void main(String args[]) {
// an array containing the data of the linked list.
int[] data = { 12, 2, 1, 15 };
// creating the head pointer
Node head = null;
// constructing the linked list from last to first
for (int i = data.length - 1; i >= 0; i--) {
head = new Node(data[i], head);
}
// printing the linked list before sorting
System.out.println("Original Linked list: ");
printList(head);
// sorting the linked list.
head = mergeSort(head);
// print linked list
System.out.println("\nSorted Linked list: ");
printList(head);
}
}
Python Code:
# creating a linked list node.
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
# insertNode function will create a new node and insert the newly created node at the last.
def insertNode(self, newData):
newNode = Node(newData)
# if the head is None then add a new Node as the first node
if self.head is None:
self.head = newNode
return
# else adding the new node to the last
# traversing till last
currentNode = self.head
while currentNode.next is not None:
currentNode = currentNode.next
# adding the node in the last.
currentNode.next = newNode
# Merging the sorted linked list.
def mergeSortedList(self, list1, list2):
# handling the base cases
if list1 == None:
return list2
if list2 == None:
return list1
result = None
# recursively merging two sorted lists
if list1.data <= list2.data:
result = list1
result.next = self.mergeSortedList(list1.next, list2)
else:
result = list2
result.next = self.mergeSortedList(list1, list2.next)
return result
# a function that will sort the linked list.
def mergeSort(self, head):
# handling the base cases
if head == None or head.next == None:
return head
# finding the mid element of the linked list
middle = self.findMiddleOfList(head)
midsNext = middle.next
# set the next middle node to None
middle.next = None
# Recursively sorting the divided linked list.
left = self.mergeSort(head)
right = self.mergeSort(midsNext)
# let the head pointer now point to the sorted linked list.
return self.mergeSortedList(left, right)
# Finding the middle part of the linked list.
def findMiddleOfList(self, head):
if (head == None):
return head
"""
using the fast-slow pointer technique, when the fast pointer reaches the end, the slow pointer will point to the mid element
"""
slow = head
fast = head
while (fast.next != None and
fast.next.next != None):
slow = slow.next
fast = fast.next.next
# returning the mid.
return slow
# a function to traverse and print the linked list.
def printList(head):
if head is None:
print(" ")
currentNode = head
while currentNode:
print(currentNode.data, end=" ")
currentNode = currentNode.next
print(" ")
if __name__ == '__main__':
# an empty linked list.
l = LinkedList()
l.insertNode(12)
l.insertNode(2)
l.insertNode(1)
l.insertNode(15)
# printing the linked list before sorting.
print("Original Linked list: ")
printList(l.head)
# sorting the linked list.
l.head = l.mergeSort(l.head)
print("Sorted Linked list: ")
printList(l.head)
Output:
Original Linked list:
12 2 1 15
Sorted Linked list:
1 2 12 15
Complexity
In the above approach, we are dividing the linked list into smaller halves and then perform some operations on it. We are also using an extra list or array in the merge operation to store the current result.
Time Complexity
The time complexity of the merge sort approach to sort a linked list comes out to be O(n∗logn), where n is several nodes in a linked list.
For more detail about the calculation of the time complexity of this divide and conquer technique, refer here.
Space Complexity
The space complexity of the merge sort approach to sort a linked list comes out to be O(n), where n is the size of the extra array or list used in the mere function.
Rearrange Linked List in Increasing Order
We have already discussed how we can sort a linked list, now arranging a linked list in increasing order is sorting a linked list. So, we will only see the sorting function that will sort the linked list or rearrange the linked list in increasing order.
Code
Let us now look at the implementation of the algorithm that we discussed previously. We will need pointers and a nested loop to arrange the linked list in increasing order.
C++ Code:
// a helper function that will set the currentNode at its correct position.
void sortListHelper(Node **head, Node *newNode) {
Node temp;
Node *current = &temp;
temp.next = *head;
// checking the current node with each node of the linked list if it is smaller then we are swapping.
while (current->next != NULL && current->next->data < newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
*head = temp.next;
}
// a function that will sort the linked list.
void sortLinkedList(Node **head) {
// a list to store the current result
Node *answerList = NULL;
/*
the current node will be pointing at the head of the linked list and the nextNode will be pointing to the second node of the linked list.
*/
Node *current = *head;
Node *nextNode;
while (current != NULL) {
/*
setting the nextNode pointer to the next node and calling the helper function that will set the current node at its correct position.
*/
nextNode = current->next;
sortListHelper(&answerList, current);
current = nextNode;
}
// finally making the head node point to the resultant sorted linked list.
*head = answerList;
}
Java Code:
// a helper function that will set the currentNode at its correct position.
public static Node sortListHelper(Node head, Node newNode) {
Node temp = new Node();
Node current = temp;
temp.next = head;
// checking the current node with each node of the linked list if it is smaller then we are swapping.
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
return temp.next;
}
// a function that will sort the linked list.
public static Node sortLinkedList(Node head) {
// a list to store the current result
Node result = null;
Node current = head;
Node nextNode;
/*
the current node will be pointing at the head of the linked list and the nextNode will be pointing to the second node of the linked list.
*/
while (current != null) {
/*
setting the nextNode pointer to the next node and calling the helper function that will set the current node at its correct position.
*/
nextNode = current.next;
result = sortListHelper(result, current);
current = nextNode;
}
/*
finally returning the resultant sorted linked list making it the head node of the sorted linked list.
*/
return result;
}
Python Code:
# a helper function that will set the currentNode at its correct position.
def sortLinkedListHelper(head, newNode):
temp = Node()
current = temp
temp.next = head
# checking the current node with each node of the linked list if it is smaller, then we are swapping.
while current.next and current.next.data < newNode.data:
current = current.next
newNode.next = current.next
current.next = newNode
return temp.next
# a function that will sort the linked list.
def sortLinkedList(head):
# a list to store the current result
answerList = None
current = head
# current node will be pointing at the head of the linked list
while current:
"""
setting the nextNode pointer to the next node and calling the helper function that will set the current node at its correct position.
"""
nextNode = current.next
answerList = sortLinkedListHelper(answerList, current)
current = nextNode
"""
finally returning the resultant sorted linked list making it the head node of the sorted linked list.
"""
return answerList
Complexity
In the algorithm to sort a linked list, we are traversing the linked list twice. In the traversal, we are only using two extra nodes.
Time Complexity
So, the time complexity of the algorithm to sort a linked list comes out to be O(n2), where n is the number of nodes in a linked list.
Space Complexity
Since we are not using any extra space in the linked list traversal, the space complexity of the algorithm to sort a linked list comes out to be O(1).
Conclusion
- A linked list is a sequential collection of data elements connected via links.
- The data element of a linked list is known as a node that contains two parts namely- the data part and the pointer. The pointer points to the next node of the linked list.
- For sorting a linked list, we can use the insertion sort type algorithm. In each iteration, one element of the linked list is moved to its correct position.
- The time complexity of the algorithm to sort a linked list comes out to be O(n2), where n is the number of nodes in a linked list. On the other hand, the space complexity of the algorithm to sort a linked list comes out to be O(1).
- We can sort a linked list using the merge sort. Merge sort is one of the divides and conquer techniques as it divides the linked list into halves until the size of the linked list is greater than equal to one.
- The idea of divide and conquer is to divide the input into smaller problems and then find the solution to those smaller problems. Once the smaller problem is solved then the results can be combined to get the solution to a larger problem.
- In the merge sort approach to sort a linked list, we are dividing the linked list into smaller halves and then performing some operations on it. We are also using an extra list or array in the merge operation to store the current result.
- The time complexity of the merge sort approach to sort a linked list comes out to be O(n∗logn), where n is the number of nodes in a linked list. On the other hand, the space complexity comes out to be O(n).
