Insertion Sort List in C++

Suppose we have a linked list, we have to perform the insertion sort on this list. So if the list is like [9,45,23,71,80,55], sorted list is [9,23,45,55,71,80].

To solve this, we will follow these steps −

• dummy := new Node with some random value
• node := given list
• while node is not null,
  • newNode = next of node, dummyHead := next of dummy, prevDummyHead := dummy
  • while true −
    • if dummyHead is not present, value of dummyHead > value of node
      • next of node := dummyHead
      • next of prevDummyHead := node
      • break the loop
    • prevDummyHead := dymmyHead, and dummyHead = next of dummy head
  • node := nextNode
• return next of dummy

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class ListNode{    public:       int val;       ListNode *next;       ListNode(int data){          val = data;          next = NULL;       } }; ListNode *make_list(vector<int> v){    ListNode *head = new ListNode(v[0]);    for(int i = 1; i<v.size(); i++){       ListNode *ptr = head;       while(ptr->next != NULL){          ptr = ptr->next;       }       ptr->next = new ListNode(v[i]);    }    return head; } void print_list(ListNode *head){    ListNode *ptr = head;    cout << "[";    while(ptr){       cout << ptr->val << ", ";       ptr = ptr->next;    }    cout << "]" << endl; } class Solution {    public:    ListNode* insertionSortList(ListNode* a) {       ListNode* dummy = new ListNode(-1);       ListNode* node = a;       ListNode* nextNode;       ListNode* dummyHead;       ListNode* prevDummyHead;       while(node != NULL){          nextNode = node->next;          dummyHead = dummy->next;          prevDummyHead = dummy;          while(1){             if(!dummyHead || dummyHead->val > node->val){                node->next = dummyHead;                prevDummyHead->next = node;                //cout << prevDummyHead->val << " " << node->val << endl;                break;             }             prevDummyHead = dummyHead;             dummyHead = dummyHead->next;          }          node = nextNode;       }       return dummy->next;    } }; main(){    vector<int> v = {5,3,2,0,-4,7};    ListNode *head = make_list(v);    Solution ob;    print_list(ob.insertionSortList(head)); }

Input

{5,3,2,0,-4,7}

Output

[-4, 0, 2, 3, 5, 7, ]