Insertion Sort List LeetCode solution in C++

1
class Solution {
2
 public:
3
  ListNode *insertionSortList(ListNode *head) {
4
    ListNode *prev = head, *cur = head->next;
5
    while (cur) {
6
      ListNode *tmp = head, *pt = NULL;
7
      while (tmp != cur and tmp->val < cur->val) {
8
        pt = tmp;
9
        tmp = tmp->next;
10
      }
11
      if (tmp == cur) {
12
        prev = prev->next;
13
        cur = cur->next;
14
        continue;
15
      }
16
      prev->next = cur->next;
17
      if (!pt) {
18
        cur->next = head;
19
        head = cur;
20
      } else {
21
        pt->next = cur;
22
        cur->next = tmp;
23
      }
24
      cur = prev->next;
25
    }
26
    return head;
27
  }
28
};