Insertion Sort List

Problem Id: 147 Difficulty: Medium


Intuition

Solution


class Solution:
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None

        sorted_head = ListNode(None)
        sorted_head.next = head
        head = head.next
        sorted_head.next.next = None

        while head:
            # pop from origin
            node = head
            head = head.next
            node.next = None

            # add into sorted
            index = sorted_head
            while index.next and index.next.val < node.val:
                index = index.next
            node.next = index.next
            index.next = node

        return sorted_head.next