1 /**
 2     Author: Vincent Zhang
 3     Problem: https://oj.leetcode.com/problems/insertion-sort-list/
 4 */
 5 class Solution {
 6 public:
 7     ListNode *insertionSortList(ListNode *head) {
 8 
 9         // check if head is NULL or has no next node, return head
10         if (head == NULL || head->next == NULL) return head;
11 
12         // pointer point to current node
13         ListNode *pCurrent = head->next;
14         // set the next node of head to NULL, which break the inputed list into 2 halves;
15         // first half begin with head, end with a NULL: the sorted part;
16         // second half contains the unsorted nodes.
17         head->next = NULL;
18         ListNode *pTemp = NULL, *index = NULL;
19         // pCurrent is not NULL, meaning not the last node
20         while (pCurrent != NULL)
21         {   
22             // save the next node of pCurrent to pTemp
23             pTemp = pCurrent->next;
24             // insertion to the head
25             if (pCurrent->val <= head->val)
26             {
27                 pCurrent->next = head;
28                 head = pCurrent;
29             }
30             else    // Find the proper position to insert
31             {
32                 index = head;
33                 while (index->next !=NULL && pCurrent->val > index->next->val)
34                     index = index->next;
35                 pCurrent->next = index->next;
36                 index->next = pCurrent;
37             }
38             pCurrent = pTemp;
39         }
40         return head;
41     }
42 };