Insertion Sort for Singly Linked List

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, and we need to sort the given list using the insertion sort technique.

Input:

Output:

Explanation: The given list has been sorted.

This question is not a tricky one.

Let us have a glance at the approach.

Approach

The approach is going to be pretty simple.

  • We will create an empty result singly linked list, which will be sorted.
  • Then, we will traverse the given linked list, and for every node that we visit, we will insert the current node in a sorted way in our result list.
  • To insert in a sorted way:
    • We will traverse our result list and keep comparing every node with our current node.
    • As soon as we find a node whose value is greater than the current node, we will insert the current node just before that node.
    • If the current node value is greater than every other node of our result list, then we will append the current node at the end.
    • To see the above process of inserting an element in a sorted list in a sorted way in more detail, check out the article link provided above in the above section.
  • After complete traversal, change the head of the given linked list to the head of the result list.
  • Finally, return the head.

Let’s move to the algorithm to see the approach in more depth.

Algorithm

  • Initialize the newly created sorted list as NULL.
  • Traverse the given singly linked list using a pointer say current.
    • For every node, while traversal, store the next of the node in a temp variable and remove all of its links.
    • Insert the current node in a sorted way in the result list.
    • Update current’s value with temp for further traversal.
  • Once the traversal is over, update the head pointer by making it point to our result list.
  • Return the head pointer.

Dry Run

Code Implementation

#include 
using namespace std;
 
struct Node {
    int val;
    struct Node* next;
    Node(int x)
    {
        val = x;
        next = NULL;
    }
};
 
class LinkedlistIS {
 
public:
    Node* head;
    Node* newhead;
 
    void push(int val)
    {

        Node* newnode = new Node(val);

        newnode->next = head;
 
        head = newnode;
    }
 
    void insertionSort(Node* headref)
    {
        newhead = NULL;
        Node* current = headref;

        while (current != NULL) {

            Node* temp = current->next;

            sortedInsert(current);
            // Update current
            current = temp;
        }

        head = newhead;
    }
    
    void sortedInsert(Node* newnode)
    {

        if (newhead == NULL || newhead->val >= newnode->val) {
            newnode->next = newhead;
            newhead = newnode;
        }
        else {
            Node* current = newhead;
 
            while (current->next != NULL
                   && current->next->val < newnode->val) {
                current = current->next;
            }
            newnode->next = current->next;
            current->next = newnode;
        }
    }

    void printlist(Node* head)
    {
        while (head != NULL) {
            cout << head->val << " ";
            head = head->next;
        }
    }
};
int main()
{
    LinkedlistIS list;
    list.head = NULL;

    list.push(3);
    list.push(1);
    list.push(2);
    list.push(4);
    list.push(5);
    cout << "Linked List before sorting" << endl;
    list.printlist(list.head);
    cout << endl;
    list.insertionSort(list.head);
    cout << "Sorted Linked List" << endl;
    list.printlist(list.head);
}
public class LinkedlistIS
{
    node head;
    node newhead;
 
    class node
    {
        int val;
        node next;
 
        public node(int val)
        {
            this.val = val;
        }
    }
 
    void push(int val)
    {

        node newnode = new node(val);

        newnode.next = head;

        head = newnode;
    }

    void insertionSort(node headref)
    {
 
        newhead = null;
        node current = headref;

        while (current != null)
        {

            node temp = current.next;

            sortedInsert(current);

            current = temp;
        }

        head = newhead;
    }

    void sortedInsert(node newnode)
    {

        if (newhead == null || newhead.val >= newnode.val)
        {
            newnode.next = newhead;
            newhead = newnode;
        }
        else
        {
            node current = newhead;

            while (current.next != null && current.next.val < newnode.val)
            {
                current = current.next;
            }
            newnode.next = current.next;
            current.next = newnode;
        }
    }

    void printlist(node head)
    {
        while (head != null)
        {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
     

    public static void main(String[] args)
    {
        LinkedlistIS list = new LinkedlistIS();

        list.push(3);
        list.push(1);
        list.push(2);
        list.push(4);
        list.push(5);
        System.out.println("Linked List before Sorting..");
        list.printlist(list.head);
        list.insertionSort(list.head);
        System.out.println("\nSorted Linked List");
        list.printlist(list.head);
    }
}

Output

Linked List before Sorting.
5 4 2 1 3
Sorted Linked List
1 2 3 4 5

Time Complexity: O(n2), as we are using nested traversal

So, in this article, we have tried to explain the most efficient approach to sort a singly linked list using the insertion sort technique. Insertion sort is an important technique, and when it gets coupled with a singly linked list, it becomes even more important. 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.

Previous post Subtract two numbers represented as Linked Lists
Next post Decimal Equivalent of Binary Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *