FASTER than 96.02%, C++, Clean Code
Insertion Sort for Linked list.\n->Create a dummy node at the start of the linked list\n->Traverse the list start till end and for each node insert it at the ri
Insertion Sort for Linked list.\n->Create a dummy node at the start of the linked list\n->Traverse the list start till end and for each node insert it at the right position by using temporary node prev that tells us the right position for the node.\n->Return the next node of dummy as that will be the starting of linked list.\n\n```\n/*\n Definition for singly-linked list.\n  struct ListNode {\n      int val;\n     ListNode next;\n     ListNode() : val(0), next(nullptr) {}\n     ListNode(int x) : val(x), next(nullptr) {}\n     ListNode(int x, ListNode next) : val(x), next(next) {}\n  };\n */\nclass Solution {\npublic:\n    ListNode insertionSortList(ListNode head) {\n        ListNode dummy=new ListNode();\n        dummy->next=head;\n        ListNode curr=head,prev=dummy;\n        while(curr){\n            if(curr->next && curr->next->val<curr->val){\n                ListNode nxt=curr->next->next;\n                ListNode insert=curr->next;              //node to be inserted at right position\n                while(prev->next->val<insert->val)\n                     prev=prev->next;                   //takes us to the last node whose value is more than the node to be inserted\n                curr->next=nxt;\n                insert->next=prev->next;\n                prev->next=insert;\n                prev=dummy;       //again initialized to dummy for next comparisions\n            }\n            else\n              curr=curr->next;\n        }\n        return dummy->next;\n    }\n};\n```
['C']