Cacher is the code snippet organizer for pro developers

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return None
        dummy = ListNode(-float('inf'))
        # dummy.next = head
        curNode = head
        # curTail = head
        # list1: list1CurNode->...->node
        # list2: dummy->..->p->..->node
        while curNode != None:
            # curNode = curTail.next
            p = dummy
            while p and p.next and p.next.val < curNode.val:
                p = p.next
            # p->curNode->p.next
            cn = curNode.next
            pn = p.next
            p.next = curNode
            curNode.next = pn
            curNode = cn
        return dummy.next