Insertion Sort List Python Solution with Tests

Tested Python solution for LeetCode 147 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 147, Medium. Topics: Linked List, Sorting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 147   # by problem number
lcpy gen -s insertion_sort_list   # by problem name

​

Problem

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

The steps of the insertion sort algorithm:

1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

​

Examples

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

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

​

Constraints

• The number of nodes in the list is in the range [1, 5000]
• -5000 <= Node.val <= 5000

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import ListNode


class Solution:
    # Time: O(n^2)
    # Space: O(1)
    def insertion_sort_list(self, head: ListNode[int] | None) -> ListNode[int] | None:
        dummy = ListNode[int](0)
        dummy.next = head
        current = head
        while current is not None and current.next is not None:
            next_node = current.next
            if current.val <= next_node.val:
                current = current.next
                continue
            current.next = next_node.next
            prev = dummy
            while prev.next is not None and prev.next.val < next_node.val:
                prev = prev.next
            next_node.next = prev.next
            prev.next = next_node
        return dummy.next

​

Complexity

Time	Space
O(n^2)	O(1)

​

Tags

NeetCode All.