147. Insertion Sort List

Medium

Problem:

Sort the linked list using insertion sort.

Input: head = [4,2,1,3]
Output: [1,2,3,4]

https://leetcode.com/problems/insertion-sort-list/

Solution:

Insertion sort divides the task into two groups: the ones that need to be sorted and the ones that have been sorted.

• We can sort by comparing the items that need sorting, head and cur.next.

• parent always points to that position.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode(0)
        while head:
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            cur.next, head.next, head = head, cur.next, head.next

            # Optimization
            if head and cur.val > head.val:
                cur = parent
        return parent.next