💢☠💫Easiest👾Faster✅💯 Lesser🧠 🎯 C++✅Python3🐍✅Java✅C✅Python🐍✅C#✅💥🔥💫Explained☠💥🔥 Beats 100
Intuition\n\n\n\n\n\n\n\n\njavascript []\n//JavaScript Code\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (v
# Intuition\n![0ehh83fsnh811.jpg](https://assets.leetcode.com/users/images/221504d7-50c3-4224-8703-e525a2fdf672_1724776353.854879.jpeg)\n![Screenshot 2024-08-27 124040.png](https://assets.leetcode.com/users/images/17c345ea-44ce-43b0-83b5-c26e4e3e5024_1724776363.6431353.png)\n![Screenshot 2024-08-27 175324.png](https://assets.leetcode.com/users/images/f55a50ca-211d-48ae-b5e5-1e488f8d0bc1_1724776370.0120647.png)\n![Screenshot 2024-08-27 180400.png](https://assets.leetcode.com/users/images/068f9b86-425e-4a94-88d0-8671afd48358_1724776375.9220643.png)\n![Screenshot 2024-08-27 182300.png](https://assets.leetcode.com/users/images/4b74f64b-a70c-4226-bf3e-3e91c0d80cbe_1724776382.07952.png)\n![Screenshot 2024-08-27 201431.png](https://assets.leetcode.com/users/images/c75b3334-2e53-4c63-8bff-34e689057b27_1724776388.8528628.png)\n![Screenshot 2024-08-27 214112.png](https://assets.leetcode.com/users/images/73d8540d-b5a0-48f7-b7b6-47576b3cc981_1724776394.8055673.png)\n![Screenshot 2024-08-27 215342.png](https://assets.leetcode.com/users/images/f21cdf87-1e82-469e-a576-cb613592c62a_1724776400.8624454.png)\n```javascript []\n//JavaScript Code\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.next = (next===undefined ? null : next)\n * }\n */\n/**\n * @param {ListNode} head\n * @return {ListNode}\n */\nvar insertionSortList = function(head) {\n    const arr = []\n    let curr = head\n    while(curr != undefined){\n        arr.push(curr.val)\n        curr = curr.next\n    }\n    \n    arr.sort((a, b) =>{\n        return a - b\n    })\n    \n    //console.log(arr)\n    curr = head\n    while(curr != undefined){\n        curr.val = arr.shift()\n        curr = curr.next\n    }\n    return head\n};\n```\n```C++ []\n//C++ Code\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        vector<ListNode*> vec;\n        while(head){\n            vec.push_back(head);\n            head = head->next;\n        }\n        sort(vec.begin(), vec.end(), [&](ListNode* a, ListNode* b){\n            return a->val > b->val;\n        });\n        \n        ListNode* prev = nullptr;\n        for(int i = 0; i < vec.size(); i++){\n            head = vec[i];\n            head->next = prev;\n            prev = head;\n        }\n        return head;\n    }\n};\n```\n```Python3 []\n#Python3 Code\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        res = []\n        while head:\n            res.append(head.val)\n            head = head.next\n        \n        res = sorted(res, reverse = True)\n        #print(res)\n        dummy = None\n        \n        for node in res:\n            head = ListNode(node)\n            head.next = dummy\n            dummy = head\n            \n        return dummy\n            \n```\n```Java []\n//Java Code\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public ListNode insertionSortList(ListNode head) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>();\n        ListNode curr = head;\n        // Get values to PQueue (insertion sort inside queue)\n        while(curr != null){\n            pq.add(curr.val);\n            curr = curr.next;\n        }\n        // Fill values into list\n        curr = head;\n        while(curr != null){\n            curr.val = pq.poll();\n            curr = curr.next;\n        }\n        return head;\n    }\n}\n```\n```C []\n//C Code\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     struct ListNode *next;\n * };\n */\ntypedef struct ListNode ListNode;\n\nListNode* newNode(int val){\n    ListNode* node = (ListNode*)malloc(sizeof(ListNode));\n    node->val = val;\n    node->next = NULL;\n    return node;\n}\nstruct ListNode* insertionSortList(struct ListNode* head) {\n        ListNode* dummy = newNode(0);\n        dummy -> next = head;\n        ListNode *pre = dummy, *cur = head;\n        while (cur) {\n            if ((cur -> next) && (cur -> next -> val < cur -> val)) {\n                while ((pre -> next) && (pre -> next -> val < cur -> next -> val)) {\n                    pre = pre -> next;\n                }\n                ListNode* temp = pre -> next;\n                pre -> next = cur -> next;\n                cur -> next = cur -> next -> next;\n                pre -> next -> next = temp;\n                pre = dummy;\n            }\n            else\n                cur = cur -> next;\n        }\n        return dummy -> next;\n}\n```\n```Python []\n#Python Code\n# Definition for singly-linked list.\n# class ListNode(object):\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution(object):\n    def insertionSortList(self, head):\n        """\n        :type head: ListNode\n        :rtype: ListNode\n        """\n        result = ListNode(-5000)\n\n        def insert(partial, toplace):\n            initial = partial\n            partial = partial.next\n            while partial != None:\n                if toplace < partial.val:\n                    break\n                initial = partial\n                partial = partial.next\n            newnode = ListNode(toplace)\n            initial.next = newnode\n            newnode.next = partial\n\n\n        while head != None:\n            insert(result, head.val)\n            head = head.next\n\n        result = result.next\n        return result\n```\n```C# []\n//C# Code\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     public int val;\n *     public ListNode next;\n *     public ListNode(int val=0, ListNode next=null) {\n *         this.val = val;\n *         this.next = next;\n *     }\n * }\n */\npublic class 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                    int x = j.val;\n                    j.val = cur.val;\n                    cur.val = x;\n                }\n            }\n        }\n        return head;\n    }\n}\n```\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n     O(N * logN)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n     O(N)\n# Code\n![th.jpeg](https://assets.leetcode.com/users/images/f0a13e89-02ae-468e-80aa-e20ad0808feb_1724776870.651186.jpeg)\n
['Linked List', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']