nikunjsoni

147

Mar 21st, 2021
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* insertionSortList(ListNode* head) {
  14.         ListNode *dummy = new ListNode(0, head);
  15.         ListNode *element, *prev, *curr;
  16.         prev = dummy; element = dummy->next;
  17.         while(element){
  18.             curr = dummy;
  19.             while(curr->next != element){
  20.                 if(curr->next->val > element->val){
  21.                     prev->next = element->next;
  22.                     element->next = curr->next;
  23.                     curr->next = element;
  24.                     element = prev->next;
  25.                     break;
  26.                 }
  27.                 else{
  28.                     curr = curr->next;
  29.                 }
  30.             }
  31.             if(curr->next == element){
  32.                 prev = element;
  33.                 element = element->next;
  34.             }
  35.         }
  36.         return dummy->next;
  37.     }
  38. };
RAW Paste Data