147: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe solution involves iterating through the linked list, removing each no
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe solution involves iterating through the linked list, removing each node from the list, and then inserting it into the sorted portion of the list. The sorted portion of the list is initially just the first node, and grows with each iteration.\n\nThis solution has a time complexity of O(n^2) since in the worst case, we may need to iterate through the entire sorted portion of the list for each node in the unsorted portion of the list. The space complexity is O(1) since we are only manipulating the existing linked list and not creating any new data structures.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def insertionSortList(self, head: ListNode) -> ListNode:\n        # Initialize the sorted portion of the list to be the first node\n        sorted_head = ListNode(0)\n        sorted_head.next = head\n        sorted_tail = head\n        \n        # Start with the second node in the list, since the first node is already sorted\n        curr = head.next\n        \n        while curr:\n            # If the current node is greater than the tail of the sorted list, \n            # it is already in the correct place, so just move on to the next node\n            if curr.val >= sorted_tail.val:\n                sorted_tail = curr\n                curr = curr.next\n            else:\n                # Remove the current node from the list\n                sorted_tail.next = curr.next\n                \n                # Find the correct position to insert the current node in the sorted list\n                insert_pos = sorted_head\n                while insert_pos.next.val < curr.val:\n                    insert_pos = insert_pos.next\n                \n                # Insert the current node into the sorted list\n                curr.next = insert_pos.next\n                insert_pos.next = curr\n                \n                # Move on to the next node in the unsorted portion of the list\n                curr = sorted_tail.next\n        \n        return sorted_head.next\n\n```
['Linked List', 'Sorting', 'Python', 'Python3']