Sorting a Singly Linked List

Given a Linked List, the task is to sort this Linked List in ascending order.

Examples:

Input: 10->30->20->5
Output: 5->10->20->30

Input: 20->4->3
Output: 3->4->20

Approach: We can sort the LinkedList by many sorting techniques:

Method 1: Sort Linked List using Bubble Sort

1. Get the Linked List to be sorted
2. Apply Bubble Sort to this linked list , in which, while comparing the two adjacent nodes, actual nodes are swapped instead of just swapping the data.
3. Print the sorted list

Below is the implementation of the above approach:

                                                                                                                     "                                                                              Java

                                                                                "                                                                             Python

Linked list before sorting 78 -> 20 -> 10 -> 32 -> 1 -> 5 -> Linked list after sorting 1 -> 5 -> 10 -> 20 -> 32 -> 78 ->

Time complexity: O(n ^ 2)
Auxiliary Space: O(1)

Method 2: Sort Linked List using Insertion Sort

Below is a simple insertion sort algorithm for a linked list.

• Create an empty sorted (or result) list
• Traverse the given list, do following for every node.
  • Insert current node in sorted way in sorted or result list.

  Below is the implementation of the above approach:

                                                                                                                                                         Java

                                                                                                                                                           Python

                                    <span Allocate a new node                                                                                                                                                   JavaScript

  
  Output

  Linked List before sorting 30 3 4 20 5 Linked List After sorting 3 4 5 20 30

  Time complexity: O(n ^ 2)
  Auxiliary Space: O(1)

  Method 3: Sort Linked List using Quick Sort

  • Call the partition function to get a pivot node placed at its correct position
    • In the partition function, the last element is considered a pivot
    • Then traverse the current list and if a node has a value greater than the pivot, then move it after the tail. If the node has a smaller value, then keep it at its current position.
    • Return pivot node

    Below is the implementation of the above approach:

                                                                                                                                                                                                                                                                             Java

                                                                                                                                                                                                                                                                                            Python

                                                                                                                                                                                                                                                                                                                                      JavaScript

    
    Output

    Linked List before sorting 30 3 4 20 5 Linked List after sorting 3 4 5 20 30

    Time complexity: O(n ^ 2)
    Auxiliary Space: O(1)

    Method 4: Sort Linked List using Merge Sort

    Let the head be the first node of the linked list to be sorted and headRef be the pointer to head. Note that we need a reference to head in MergeSort() as the below implementation changes next links to sort the linked lists (not data at the nodes), so the head node has to be changed if the data at the original head is not the smallest value in the linked list.

    • MergeSort(headRef)
      • If the head is NULL or there is only one element in the Linked List, then return.
      • Else divide the linked list into two halves.
        • FrontBackSplit(head, &a, &b); /* a and b are two halves */
        • MergeSort(a);
        • MergeSort(b);
        • *headRef = SortedMerge(a, b);

        Below is the implementation of the above approach:

                                                                                                                                                                                                                         <span Created lists shall be a: 2->3->20->5->10->15 */                      C

                                                                                                                                                                                                                                               <span Created lists shall be a: 2->3->20->5->10->15 */                     Java

                                                                                                                                                                                                                                        <span Created list shall be a: 2->3->20->5->10->15                              Python

         <span Python3 program to merge sort of linked list           middle of the list          3->20->5->10->15  C#

                                                                                                                                                                                                                                      <span Created list shall be: 2->3->20->5->10->15                         JavaScript

        
        Output

        Sorted Linked List is: 2 3 5 10 15 20

        Time complexity: O(n log n)
        Auxiliary Space: O(1)