✅ [Python] Dummy Head || Clean and Easy to Understand with Detailed Explanation
Time Complexity : O(N2) \nSpace Complexity : O(1)\nDummy head can make the code more concise\n\nclass Solution(object):\n    def insertionSortList(self, head):\
**Time Complexity : O(N<sup>2</sup>) \nSpace Complexity : O(1)**\n**Dummy head can make the code more concise**\n```\nclass Solution(object):\n    def insertionSortList(self, head):\n        p, sl = head, ListNode()  # sl is the sortedList with dummy head node.\n        while p:  # traverse the input linked list until None\n            q = sl  # q is the pre of current node of sortedList\n            while q.next and q.next.val < p.val:  # find the insertion position sequentially\n                q = q.next\n            p.next, q.next, p, q = q.next, p, p.next, q.next  # insert p to q.next\n        return sl.next  # Note sl is the dummy head node\n```\n**If you have any question, feel free to ask. If you like the solution or the explaination, Please UPVOTE!**
['Python']