Sorting and Merging Single Linked List
In the last article, we started our discussion about the linked list. We saw what the linked list is along with its advantages and disadvantages. We also studied some of the most commonly used linked list method such as traversal, insertion, deletion, searching, and counting an element. Finally, we saw how to reverse a linked list.
In this article, we will continue from where we left in the last article and will see how to sort a linked list using bubble and merge sort, and how to merge two sorted linked lists.
Before we continue, it is imperative to mention that you should create Node and LinkedList classes that we created in the last article.
Sorting a Linked List using Bubble Sort
There are two ways to sort a linked list using bubble sort:
- Exchanging data between nodes
- Modifying the links between nodes
In this section, we will see how both these approaches work. We will use the bubble sort algorithm to first sort the linked list by changing the data, and then we will see how we can use bubble sort to change the links in order to sort the linked list.