15-line easy to understand Python solution


  • 0
    T

    It would be of 14 lines if I don't break the really long line.

    class Solution(object):
        def insertionSortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head or not head.next:
                return head
            pre_head = ListNode(None)
            pre_head.next = head
            sorted_end, cur = head, head.next
            while cur:
                if cur.val >= sorted_end.val:
                    sorted_end, cur = sorted_end.next, cur.next
                else:
                    pre, ptr = pre_head, pre_head.next
                    while cur.val >= ptr.val:
                        pre, ptr = ptr, ptr.next
                    sorted_end.next, pre.next, cur.next, cur = (
                        cur.next, cur, ptr, sorted_end.next.next)
            return pre_head.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.