题解 | #对链表进行插入排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        ListNode* p = head;
        while(p->next)
        {
            // 去找到这个比前一个值小的结点位置
            while(p->next && p->next->val > p->val)
                p = p->next;
            // 如果为空 则 返回
            if(p->next == nullptr) return head;
            // 如果不为空 则 找到异常值 位置 选择合适的位置进行插入
            ListNode* tmp = new ListNode(p->next->val);
            // 加入比头结点小，直接插到头结点位置
            if(tmp->val < head->val)
            {
                tmp->next = head;
                head = tmp;
            }
            // 否则找到合适的位置插入
            else
            {
                // 从头结点位置开始找到合适的位置
                ListNode* t = head;
                // 插入的位置的值 一定是比前一个值大 
                while(t->next && t->next->val < tmp->val)
                    t = t->next;
                // 插入操作
                tmp->next = t->next;
                t->next = tmp;
            }
            // 跳过被插入的位置，因为已经有序了
            p->next = p->next->next;
        }
        return head;
    }
};