输入：指向第一个节点的指针head

准备工作

定义链表结构，输出链表，初始化链表

struct ListNode{
    explicit ListNode(int n):val(n){}
    int val;
    struct ListNode* next= nullptr;
};

ListNode* List_init(int num){
    auto *head = new ListNode(1);
    ListNode *p = head;
    for (int i=2;i<=num;i++) {
        auto q=new ListNode(i);
        p->next=q;
        p=q;
    }
    return head;
}

void showoff(ListNode* head){
    auto p=head;
    while (p){
        cout<<p->val<<" ";
        p=p->next;
    }
    cout<<endl;
}

BM1 翻转链表

要求：翻转整个链表，输出指向翻转后的第一个节点指针

思路：遍历链表，头插生成新链表

ListNode* reverse_list(ListNode* head){
    if (head== nullptr||head->next== nullptr){
        return head;
    }
    auto new_head = new ListNode(0);
    auto p = head;
    while (p){
        auto new_node = new ListNode(p->val);
        new_node->next=new_head->next;
        new_head->next=new_node;
        p=p->next;
    }
    return new_head->next;
}

BM2 翻转链表指定区间

BM3 分组翻转链表

两题一起考虑

封装一个函数，输入一个一对指针，分别指向待翻转链表分组第一个节点前一个节点（即前一组末或理解为加装头节点）与本组末节点，输出一对指针，分别指向翻转后的组头与组末

pair<ListNode*, ListNode*> reverseBetween(ListNode* head, ListNode* end){
    // 翻转head->next到end
    if (head== nullptr||head->next== nullptr){
        return {head,end};
    }
    auto new_head = new ListNode(0);
    auto p = head->next;
    auto new_end = new ListNode(p->val);
    new_head->next=new_end;
    p=p->next;
    while (p!=end->next){
        auto new_node = new ListNode(p->val);
        new_node->next=new_head->next;
        new_head->next=new_node;
        p=p->next;
    }
    return {new_head->next,new_end};
}

利用此函数完成两题，均加装头节点

ListNode* reverseBetween(ListNode* head,int m,int n){
    if (m>n||head== nullptr||head->next== nullptr){
        return head;
    }
    auto newhead = new ListNode(0);
    newhead->next=head;
    auto verse_head = newhead;
    auto verse_end= head;
    while (--m){
        verse_head=verse_head->next;
    }
//    cout<<verse_head->val<<endl;
    while (--n){
        verse_end=verse_end->next;
    }
//    cout<<verse_end->val<<endl;
    auto (p)= reverseBetween(verse_head,verse_end);
//    showoff(p.first);
    verse_head->next=p.first;
    p.second->next=verse_end->next;
    return newhead->next;
}

ListNode* reverseKGroup(ListNode* head, int k)  //按分组翻转
{
    auto newhead = new ListNode(0);
    newhead->next=head;
    auto p=newhead,q=newhead;
    //p指向翻转组前组末，q指向本组末
    while (true){
        int count=k;
        while (count--)
        {
            q=q->next;
            if (q== nullptr){
                return newhead->next;
            }
        }
        auto r=reverseBetween(p,q);
        p->next=r.first;
        r.second->next=q->next;
        q=r.second;
        p=q;
    }
}