递归版非递归版翻转链表

作者: 小幸运Q | 来源:发表于2021-04-12 19:26 被阅读0次

递归版非递归版翻转链表
链表的操作和算法相关
二叉树先序、中序，后序遍历的非递归，非递归实现
合并两个排序的链表
快速排序
链表
反转链表（java实现）
二叉树遍历（递归+迭代）
java中查找算法整理
二叉树的遍历(一)(递归和非递归)

递归版

last指向最后一个节点5(也就是翻转结束后的头节点，递归里面直接return 不需要修改)，(head.next).next=head 负责把当前的 ... -> 3 -> 4 变成 3 <- 4，然后3->null，因为它现在是队头变队尾。

#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
    int id;
    Node*next;
    Node(int i){
        id=i;
        next=nullptr;
    }
}Node;
// 反转操作
Node* rev(Node* &node,int k){
    if(k==0){
        return node;
    }
    if(node->next==nullptr){
        return node;
    }
    Node*last=rev(node->next,k-1);
    node->next->next=node;
    node->next=nullptr;
    return last;
}
// 从后往前k个一组反转
Node* reverse(Node*&root,int n,int k){
    Node* Root=new Node(11);
    Root->next=root;
    Node* left;
    while(n>=k){
        left=Root;
        n-=k;
        for(int i=0;i<n;i++){
            left=left->next;
        }
        // head == left (left->next,...,tail)(tail->next,...,)
        left->next=rev(left->next,k);
    }
    return Root->next;
}
Node* Init(Node*&root,vector<int>v,int index){
    if(index>=v.size()){
        return nullptr;
    }
    else{
        if(root==nullptr){
            root=new Node(v[index]);
            root->next=Init(root->next,v,index+1);
        }
        else{
            root->next=Init(root->next,v,index+1);
        }
    }
    return root;
}
void print(Node *root){
    while(root!=nullptr){
        cout<<root->id<<"  "<<&root->id<<endl;
        root=root->next;
    }
}
int main(){
    vector<int>v{1,2,3,4,5,6,7};
    Node*root=nullptr;
    Init(root,v,0);
    root=reverse(root,v.size(),3);
    print(root);
}

非递归版

(head) (head->next,...已反转链表...,tail) (tail->next,待反转链表...)
将tail->next插入到head和head->next之间。

#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
    int id;
    Node*next;
    Node(int i){
        id=i;
        next=nullptr;
    }
}Node;
Node* reverse(Node*&root,int n,int k){
    Node* Root=new Node(11);
    Root->next=root;
    Node* left;
    while(n>=k){
        left=Root;
        n-=k;
        for(int i=0;i<n;i++){
            left=left->next;
        }
        // head == left (left->next,...,tail)(tail->next,...,)
        Node* tail=left->next;
        for(int i=0;i<k-1;i++){
            Node*tailnext=tail->next;
            Node*leftnext=left->next;
            left->next=tailnext;
            tail->next=tailnext->next;
            tailnext->next=leftnext;
        }
    }
    return Root->next;
}
Node* Init(Node*&root,vector<int>v,int index){
    if(index>=v.size()){
        return nullptr;
    }
    else{
        if(root==nullptr){
            root=new Node(v[index]);
            root->next=Init(root->next,v,index+1);
        }
        else{
            root->next=Init(root->next,v,index+1);
        }
    }
    return root;
}
void print(Node *root){
    while(root!=nullptr){
        cout<<root->id<<"  "<<&root->id<<endl;
        root=root->next;
    }
}
int main(){
    vector<int>v{1,2,3,4,5,6,7};
    Node*root=nullptr;
    Init(root,v,0);
    root=reverse(root,v.size(),3);
    print(root);
}