From 3fe957fb772e60f8e04fb586dedae23ba71a938e Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Wed, 26 Aug 2020 23:47:14 +0800
Subject: import(solutions): Add problem 147 .

---
 works/solutions/cpp/147.cpp | 56 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
 create mode 100644 works/solutions/cpp/147.cpp

(limited to 'works/solutions/cpp/147.cpp')

diff --git a/works/solutions/cpp/147.cpp b/works/solutions/cpp/147.cpp
new file mode 100644
index 0000000..c741290
--- /dev/null
+++ b/works/solutions/cpp/147.cpp
@@ -0,0 +1,56 @@
+#include <cstddef>
+
+struct ListNode
+{
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+class Solution
+{
+public:
+    ListNode *insertionSortList(ListNode *head)
+    {
+        if (head == NULL)
+            return NULL;
+        if (head->next == NULL)
+            return head;
+
+        ListNode *next_sort = head->next;
+
+        head->next = nullptr;
+
+        while (next_sort != nullptr)
+        {
+            ListNode *current_sort = next_sort;
+            next_sort = current_sort->next;
+
+            ListNode *prev = nullptr;
+            ListNode *current = head;
+
+            int i = 0;
+
+            while (current != nullptr && current->val < current_sort->val)
+            {
+                i++;
+                prev = current;
+                current = current->next;
+            }
+
+            if (prev == nullptr)
+            {
+                current_sort->next = head;
+                head = current_sort;
+            }
+            else
+            {
+                ListNode *prev_next = prev->next;
+                prev->next = current_sort;
+                current_sort->next = prev_next;
+            }
+        }
+
+        return head;
+    }
+};
-- 
cgit v1.2.3