PU Insertion Sort List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head) {
    struct ListNode dummy, *l = &dummy, *r = head;
    dummy.next = 0;
    while (r) {
        l = &dummy;
        while (l->next && l->next->val < r->val) l = l->next;
        struct ListNode *nextr = r->next;
        r->next = l->next;
        l->next = r;
        r = nextr;
    }
    return dummy.next;
}

# 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 not head or not head.next: return head
        dummy = ListNode(0)
        cur = head
        while cur:
            p = dummy
            while p.next and cur.val > p.next.val:
                p = p.next
            _cur = cur.next
            p.next, cur.next = cur, p.next
            cur = _cur
        return dummy.next