1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* insertionSortList(ListNode* head) {12         if (head == nullptr) return nullptr;13         else {14             ListNode dummy(INT_MIN);  // 这里需要考虑如果数组中含有INT_MIN的情况15             dummy.next = head;16             ListNode* prev = head;17             ListNode* curr = head->next;18             while (curr != nullptr) {19                 ListNode* ptr = &dummy;20                 if (curr->val < prev->val) {21                     ListNode* tmp = curr->next;22                     ListNode* beforePtr = nullptr;23                     while (ptr->val <= curr->val) {  // 这里需要有等号，处理数组中含有INT_MIN的情况24                         beforePtr = ptr;25                         ptr = ptr->next;26                     }27                     beforePtr->next = curr;   // 注意指针的修改28                     curr->next = ptr;29                     curr = tmp;30                 } else {31                     prev->next = curr;      // 注意指针的修改32                     prev = prev->next;33                     curr = curr->next;34                 }35             }36             prev->next = curr;37             return dummy.next;38         }39     }40 };