LeetCode 147. 对链表进行插入排序

LeetCode 147. 对链表进行插入排序

思路：

构造一个链表，然后遍历原链表的每个节点p，在构造的链表中找到第一个大于当前节点p的节点的前一个节点，然后将p插入到该节点的前面。

代码：

/**
 * Definition for singly-linked list.
 * 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) {
        auto dummy = new ListNode(-1);

        for(auto p = head;p;){
            auto cur = dummy;
	    //这个地方需要提前存储一下，否则在下面更新p的时候，原始的节点next信息丢失。
            auto next = p->next;
            //在构造的链表中找到第一个大于当前节点p的节点的上一个节点cur
            while(cur->next && cur->next->val <= p->val) cur = cur->next;
            p->next = cur->next;
            cur->next = p;
            p = next;
        }
        return dummy->next;
    }
};