算法纯小白的学习日记Day1

今天研究一下昨天没写出来的链表题leetcode25题

/**
 * 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:
pair<ListNode*,ListNode*>myreverse(ListNode*head,ListNode*tail){
    ListNode*pre=tail->next;//这里的pre是因为在转置之中tail->next将会变成head-next
    ListNode*cur=head;//每次改变链表都用cur来改变
    while(pre!=tail){
        ListNode*next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return {tail,head};//返回一个新的头和尾
}
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode*hair=new ListNode(0);//设置一个dummy来方便最后输出链表
        hair->next=head;
        ListNode*pre=hair;
        while(head){
            ListNode*tail=pre;
            for(int i=0;i<k;i++){
                tail=tail->next;
                if(!tail){
                    return hair->next;//当tail到结尾时候，代表这个函数已经运行完毕了，所有
//以直接返回答案
                }
            }
            ListNode*next=tail->next;
            tie(head,tail)=myreverse(head,tail);
            pre->next=head;
            tail->next=next;
            pre=tail;//快速得到pre；
            head=tail->next;//快速得到head
        }
        return hair->next;
 
    }
};

这里还用到了pair来将head和tail链接在一起