Beginner Friendly using sorting in o(1) space
\n# Approach\nCreating a new linkedlist using insertion sotr\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n\n/**\n * Definit
\n# Approach\nCreating a new linkedlist using insertion sotr\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\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* ptr=head;\n        ListNode *nh=NULL;\n        ListNode *f=NULL;\n        while(ptr!=NULL){\n            f=ptr->next;\n            ptr->next=NULL;\n            if(nh==NULL){\n                nh=ptr;\n            }\n            else{\n                if(nh->val>ptr->val){\n                    ptr->next=nh;\n                    nh=ptr;\n                }\n                else{\n                    ListNode *tem=nh;\n                    while(tem->next!=NULL && tem->next->val<ptr->val){\n                        tem=tem->next;\n                    }\n                    if(tem->next!=NULL){\n                        ptr->next=tem->next;\n                        tem->next=ptr;\n                    }\n                    else{\n                        tem->next=ptr;\n                    }\n                }\n            }\n            ptr=f;\n        }\n        return nh;\n    }\n};\n```
['Linked List', 'C++']