备战复试，每日三题Day22

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list

插入排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //插入排序版本  通过用例：26/28    会超时
        if(head==nullptr||head->next==nullptr) return head;
        ListNode *node=new ListNode();
        node->next=head;
        head=node;
        ListNode* p=head->next;
        ListNode* q,* r,*u;
        //划分有序区和无序区
        head->next=nullptr;
        while(p!=nullptr){
            r=head,u=head->next;
            //保证每次将无序区的第一个元素插入到有序区r,u所指的节点之间，不满足则移动r,u指针
            while(u!=nullptr&&u->valval){
                r=u;
                u=u->next;
            }
            //插入到r,u之间,记录无序区的下一个元素
            q=p->next;
            p->next=u;
            r->next=p;
            p=q;
        }
        return head->next;
    }
};

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares

class Solution {
public:
    int numSquares(int n) {
        //动态规划
        //v1表示和为n的完全平方数的最小数量
        vector v1(n+1);
        for(int i=1;i<=n;i++){
            int min=INT_MAX;
            //平方数的范围为1~sqrt(n)
            for(int j=1;j*j<=i;j++){
                //每次取个数最小的
                min=fmin(min,v1[i-j*j]);
            }
            //对于每个数都保存着最少次数
            v1[i]=min+1;
        }
        //则，对于n次数最小则为v1[n]
    return v1[n];
        
    }
};

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //设置虚节点
        ListNode *dummy=new ListNode(0);
        dummy->next=head;
        ListNode *pre=dummy;
        //pre指向要反转节点的前一个节点处
        for(int i=0;inext;
        }
        ListNode *cur=pre->next;
        ListNode *back;
        //pre一直指向反转区间的前一个结点
        for(int i=0;inext;
            cur->next=back->next;
            back->next=pre->next;
            pre->next=back;
        }
        return dummy->next;

    }
      
};