Insertion Sort List LeetCode solution in Python

1
/**
2
 * Definition for singly-linked list.
3
 * class ListNode {
4
 *     val: number
5
 *     next: ListNode | null
6
 *     constructor(val?: number, next?: ListNode | null) {
7
 *         this.val = (val===undefined ? 0 : val)
8
 *         this.next = (next===undefined ? null : next)
9
 *     }
10
 * }
11
 */
12

13
function insertionSortList(head: ListNode | null): ListNode | null {
14
  if (!head) return null
15
  if (!head.next) return head
16

17
  let output = head
18
  let curr = head.next
19

20
  head.next = null
21

22
  while (curr) {
23
    const next = curr.next
24
    const insertion = curr
25

26
    output = insert(output, insertion)
27
    curr = next as ListNode
28
  }
29

30
  return output
31
}
32

33
function insert(head: ListNode, other: ListNode) {
34
  let curr = head
35
  const val = other.val
36

37
  if (val <= head.val) {
38
    other.next = head
39
    return other
40
  }
41

42
  while (curr) {
43
    if ((val > curr.val && curr.next && val <= curr.next.val) || !curr.next) {
44
      other.next = curr.next
45
      curr.next = other
46

47
      return head
48
    }
49

50
    curr = curr.next as ListNode
51
  }
52

53
  return head
54
}