#147

Insertion Sort List

specialist · 760 · lc medium +31 · verified · 58.6% accepted · 3,391 likes · top 55%

Description

Given the head of a singly linked list, sort it using insertion sort and return the sorted list's head.

The insertion sort algorithm:

- Build a sorted output list one element at a time by consuming the input.

- For each new element, find its correct position in the sorted portion and insert it there.

- Repeat until all input elements have been placed.

Example 1:

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

Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]

Output: [-1,0,3,4,5]

Code

# 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]:

# 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]: