Insertion Sort List — LeetCode 147 Python Solution
MediumLinked ListSorting
- Problem
- #147
- Pattern
- Linked List
- Reading time
- 4 min
- Source
- leetcode.com
The 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: Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
Example
- Input
- head = [4,2,1,3]
- Output
- [1,2,3,4]
Python solution
Python
# 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: ListNode) -> ListNode:
if head is None or head.next is None:
return head
dummy = ListNode(head.val, head)
pre, cur = dummy, head
while cur:
if pre.val <= cur.val:
pre, cur = cur, cur.next
continue
p = dummy
while p.next.val <= cur.val:
p = p.next
t = cur.next
cur.next = p.next
p.next = cur
pre.next = t
cur = t
return dummy.nextComplexity
| Measure | Complexity |
|---|---|
| Time | O(n log n) |
| Space | O(1) to O(n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 147. Insertion Sort List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 147. Insertion Sort List?
- LeetCode 147. Insertion Sort List is rated Medium on LeetCode.
- What topics does LeetCode 147. Insertion Sort List cover?
- LeetCode 147. Insertion Sort List is tagged Linked List and Sorting on LeetCode.