# 147. Insertion Sort List
Difficulty: Easy

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-10-13
**/
#include <cstdio>
#include <cstdlib>

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
 public:
  ListNode *insertionSortList(ListNode *head) {
    if (head == nullptr) {
      return nullptr;
    }

    ListNode pre_node;
    while (head != nullptr) {
      auto *current = head;
      head = head->next;
      insertToCorrectPosition(&pre_node, current);
    }

    ListNode *sorted_list = pre_node.next;
    return sorted_list;
  }

 private:
  void insertToCorrectPosition(ListNode *pre_node, ListNode *current) {
    while (pre_node != nullptr) {
      if (pre_node->next == nullptr) {
        pre_node->next = current;
        current->next = nullptr;
        break;
      }

      if (pre_node->next->val >= current->val) {
        auto *temp = pre_node->next;
        pre_node->next = current;
        current->next = temp;
        break;
      }

      pre_node = pre_node->next;
    }
  }
};

int main(int argc, char *argv[]) {
  ListNode *head =
      new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));

  Solution solution;
  head = solution.insertionSortList(head);

  auto *node = head;
  while (node != nullptr) {
    printf("%d,", node->val);
    auto *temp = node;
    node = node->next;
    delete temp;
  }
  printf("\n");

  return EXIT_SUCCESS;
}

## Result

Success
Details
Runtime: 52 ms, faster than 48.99% of C++ online submissions for Insertion Sort List.
Memory Usage: 9.7 MB, less than 64.86% of C++ online submissions for Insertion Sort List.

###### tags: `LeetCode-Easy` `C++`