We need to sort the given linked list using insertion sort\n\n---\n\n\u2714\uFE0F ***Solution - I (Sort by Swapping Values)***\n\nA **pseudocode for standard insertion sort** might look like this -\n\n```c\nfor i = 0 to n\n\tcur = A[i] and j = i - 1\n\twhile j >= 0 and arr[j] > cur:\n\t\tarr[j+1] = arr[j] // shift right till we find greater than cur\n\t\tj = j-1\n\tarr[j+1] = cur // insert cur at correct pos\n```\n\nThis works for array and can even work for doubly linked-list where we can traverse backwards as well. However, for a singly linked list, we cant traverse backward and thus we cant directly implement in the above approach. \n\nSo, instead of beginning to left of current element and right-shifting each element till we find correct position for `cur`, we can modify the approach and begin inner iteration from 0 till we reach `i` (current element position) and swap the values whenever `A[j] > A[i]`. At the end, this will effectively achieve the same result as standard insertion sort does after each step.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n ListNode* insertionSortList(ListNode* head) {\n for(auto cur = head; cur; cur = cur -> next) \n for(auto j = head; j != cur; j = j -> next) \n if(j -> val > cur -> val) \n swap(j -> val, cur -> val);\n return head; \n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def insertionSortList(self, head):\n cur = head\n while cur:\n j = head\n while j != cur:\n if j.val > cur.val: \n j.val, cur.val = cur.val, j.val\n j = j.next\n cur = cur.next\n return head\n```\n\n**Java**\n```java\nclass Solution {\n public ListNode insertionSortList(ListNode head) {\n for(ListNode cur = head; cur != null; cur = cur.next) \n for(ListNode j = head; j != cur; j = j.next) \n if(j.val > cur.val)\n j.val = j.val ^ cur.val ^ (cur.val = j.val); // swap \n return head;\n }\n}\n```\n\n***Time Complexity :*** O(N²)\n***Space Complexity :*** `O(1)`, only constant space is being used\n\n---\n\n\u2714\uFE0F ***Solution - II (Sort by Swapping Nodes)***\n\nIn the above solution, we required to iterate all the way from `head` till `cur` node everytime. Moreover, although each step outputs same result as insertion sort, it doesnt exactly functions like standard insertion sort algorithm in the sense that we are supposed to find & insert each element at correct position\n\nBasically, Insertion sort works by finding the correct position of `cur` in the sorted portion of list and inserting it at that position. This is particularly beneficial in case of linked list since we can remove `cur` from its position and insert `cur` at its correct position of sorted list in `O(1)` by simply manipulating pointers/links and thus we dont even need right-shift assignments as in case of arrays.\n\nWe can find correct position of `cur` by iterating in sorted portion of list till we find a node which has value less than cur. Then we remove `cur` from its original position and insert it at its correct position. The steps can be stated as -\n1. Update next pointer of `cur` to `j` which is the position before which `cur` needs to be inserted. **`cur -> next = j`**\n2. Update next pointer of previous node of `j` (`jPrev`) to `cur`. This is because `cur` is now inserted before `j` and thus `jPrev`\'s next node should point at cur. **`jPrev -> next = cur`**\n3. Update next pointer of previous node of `cur` (`curPrev`) to next of `cur`. This is because `cur` was removed from its original position and thus `curPrev` should point to next of `cur`. **`curPrev -> next = curNext`**\n4. The current node is now placed at its proper position and all pointers have been updated. Now, move on to next node and continue this process till we reach the end of list.\n\nThe below illustration will help better understand the process -\n\n```python\nConsider that we are at cur=2 and we found its correct position is before the node j=3\n\n jPrev j curPrev cur\n 1 \u2192 \'3\' \u2192 4 \u2192 5 \u2192 \'2\' \u2192 6 => 1 \u2192 2 \u2192 3 \u2192 4 \u2192 5 \u2192 6\n\n\n 2\uFE0F\u20E3\n \u21B1 \u2192 \u2192 \u2192 \u2192 \u21B4 curPrev cur\n=> 1 \u2508 \'3\' \u2192 4 \u2192 5 \u2508 \'2\' \u2508 6 => 1 \u2192 2 \u2192 3 \u2192 4 \u2192 5 \u2192 6\n \u2B11 \u2190 \u2190 \u2193 \u21B2 \u2191\n\t 1\uFE0F\u20E3 \u21B3 \u2192 \u2192 \u2B0F \n\t \t \t \t 3\uFE0F\u20E3\n```\n\nAnother thing to note is that `curPrev` only gets updated when `cur` is already at its correct position. In all other cases, curPrev will remain same becase `cur` is removed from its original position and inserted somewhere back. So when we move to the next node, `curPrev` will remain its previous node.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n ListNode* insertionSortList(ListNode* head) {\n auto dummy = new ListNode(INT_MIN, head);\n for(auto curPrev = head, cur = head -> next; cur;) {\n auto jPrev = dummy, j = jPrev -> next, curNext = cur -> next;\n if(cur -> val > curPrev -> val) // cur already at correct position...so no need to update cur\n curPrev = cur; // only case where curPrev will need to be updated\n else {\n while(j -> val < cur -> val)\n jPrev = j, j = j -> next;\n cur -> next = j; // 1\uFE0F\u20E3\n jPrev -> next = cur; // 2\uFE0F\u20E3\n curPrev -> next = curNext; // 3\uFE0F\u20E3 \n }\n cur = curNext; // move to next node now \n }\n return dummy -> next;\n }\n};\n```\n\n

\n
\n
Maintain Less Variables
\n\nWe can do away with using lesser variable names. Since we have access to next nodes, we can only maintain `jPrev` and `curPrev` and still have access to `j` and `cur`. The below solution has updated `j` and `cur` to denote `jPrev` and `curPrev` but kept the same name for simplicity.\n\n```cpp\nclass Solution {\npublic:\n ListNode* insertionSortList(ListNode* head) {\n auto dummy = new ListNode(INT_MIN, head), cur = head;\n while(cur -> next) \n if(cur -> next -> val > cur -> val) \n cur = cur -> next;\n else {\n auto j = dummy, curNextNext = cur -> next -> next;\n while(j -> next -> val < cur -> next -> val)\n j = j -> next;\n cur -> next -> next = j -> next;\n j -> next = cur -> next;\n cur -> next = curNextNext;\n }\n \n return dummy -> next;\n }\n};\n```\n\n
\n

\n\n**Python**\n```python\nclass Solution:\n def insertionSortList(self, head):\n dummy, cur_prev, cur = ListNode(-1, head), head, head.next\n while cur:\n j_prev, j, cur_next = dummy, dummy.next, cur.next\n if cur.val > cur_prev.val:\n cur_prev = cur\n else: \n while j.val < cur.val:\n j_prev, j = j, j.next\n cur.next = j\n j_prev.next = cur\n cur_prev.next = cur_next\n cur = cur_next\n return dummy.next\n```\n\n**Java**\n```java\nclass Solution {\n public ListNode insertionSortList(ListNode head) {\n ListNode dummy = new ListNode(-1, head), curPrev = head, cur = head.next;\n while(cur != null) {\n ListNode jPrev = dummy, j = jPrev.next, curNext = cur.next;\n if(cur.val > curPrev.val) curPrev = cur;\n else {\n while(j.val < cur.val) {\n jPrev = j; \n j = j.next;\n }\n cur.next = j;\n jPrev.next = cur;\n curPrev.next = curNext;\n }\n cur = curNext;\n }\n return dummy.next;\n }\n}\n```\n\n***Time Complexity :*** O(N²)\n***Space Complexity :*** `O(1)`, only constant space is being used\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---

Insertion Sort List

Problem Description

Problem Description

Answer Panel