ACM模式链表输入&手撕k组反转链表_acm链表 输入

 面试手撕的时候遇到了，自己没处理好，做过的题想不出来，气死，以此谨记。

 ACM模式链表输入

#include <iostream>
#include <vector>
using namespace std;
struct Node{
  int val;
  Node* next;
  Node(int v): val(v), next(nullptr){}
};
Node* creat(vector<int>& arr){
    Node* head = new Node(-1);
    Node* pre = head;
    for(auto& a:arr){
        Node* t = new Node(a);
        pre->next = t;
        pre = t;
    }
    return head;
}
int main(){
    vector<int> arr{1,2,3,4,5,6,7,8};
    Node* L = creat(arr);
    Node* t = L;//可选
    L = L->next;//记得!!!
    delete t;//可选
    t = nullptr;//可选
    /*
        调用你的函数方法
        t = func(L);
    */
    while(t != nullptr){
        cout << t->val;//打印
        Node* tmp = t;//可选
        t = t->next;  
        delete tmp; //可选
    }
    return 0;
}

k个一组反转链表Leetcode25

官方的简单操作：递归

拆分问题：每次反转1组

返回值：反转后的头节点

边界条件：空或长度不到k个

Node* reversek(Node* l, int k){
    if(k == 1 || l == nullptr) return l;
    Node* tail = l;
    for(int i = 0; i < k; ++i){//判断长度是否满足反转条件
        if(tail == nullptr) return l;
        tail = tail->next;
    }
    //循环结束时，tail指向下一组的头！
    Node* pre = l;
    Node* cur = l->next;
    while(cur != tail){//只需要处理k-1次
        Node* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    } 
    //循环结束时，pre指向反转后的新头，cur指向下一组的头。
    l->next = reversek(cur, k);//l是反转后的尾节点，递归反转下一组。
    return pre;
}

面试时手撕的复杂操作。。。 循环

Node* reversek(Node* l, int k,int len){
    if(k == 1) return l;
    Node *dummy = new Node(-1);
    dummy -> next = l;
    Node * pre = dummy;//分组的头节点的前置节点
    Node * cur = l;
    for(int i = 0; i + k <= len; i += k){
        Node * head = cur;//反转前的头 
        Node * p = cur;//处理反转的前置节点
        cur = cur->next;//从第二个节点开始处理反转
        for(int j = 0; j < k - 1; j++){//反转K-1次
            Node * tmp = cur->next;
            cur->next = p;
            p = cur;
            cur = tmp;
        }
        //循环结束时，p指向新的头，cur指向下一组的头
        head->next = cur;//反转前的头作为反转后的最后一个节点
        pre->next = p;//反转前的头的前置节点连接新头
        pre = head; //更新下一组头的前置节点
    }
    Node* res = dummy->next;
    delete dummy;
    return res;
}