递归，迭代，堆栈三种方式实现单链表反转（C++）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了递归，迭代，堆栈三种方式实现单链表反转（C++），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1767字，纯文字阅读大概需要3分钟。

内容图文

#include <stack>
using namespace std;
 
struct Node
{
    int val;
    Node *next;
};
 
Node * creat_link()
{
    Node *head=NULL;
    Node *current=NULL;
    Node *tmp=NULL;
    int val=0;
    int num_node=10;
    for(int i=0;i<num_node;i++)
    {
        val=i+1;
        if(i==0)
        {
            current=(Node*)new(Node);
            current->val=val;
            current->next=NULL;
            head=current;
        }
        else
        {
            tmp=(Node*)new(Node);
            tmp->val=val;
            tmp->next=NULL;
            current->next=tmp;
            current=current->next;
 
        }
    }
    return head;
}
 
void show_display_link(Node * head)
{
    Node * current=head;
    while(current!=NULL)
    {
        cout<<current->val<<endl;
        current=current->next;
 
    }
    cout<<"finish!"<<endl;
}
 
Node * reverse_iteration_version(Node * head)
{
    Node * current=NULL;
    Node * next_node=NULL;
    Node * pre=NULL;
    current=head;
    pre=head;
    next_node=current->next;
    current->next=NULL;
    while(next_node!=NULL)
    {
        pre=current;
        current=next_node;
        next_node=next_node->next;
        current->next=pre;
    }
    head=current;
    return head;
}
 
Node * reverse_stack_version(Node * head)
{
    stack <Node * > stack_for_link;
    Node * current,* tmp,*new_head;
    current=head;
    while(current!=NULL)
    {
        stack_for_link.push(current);
        current=current->next;
    }
    current=stack_for_link.top();
    stack_for_link.pop();
    new_head=current;
    while(!stack_for_link.empty())
    {
        tmp=stack_for_link.top();
        stack_for_link.pop();
        cout<<tmp->val<<endl;
        current->next=tmp;
        current=tmp;
    }
    tmp->next=NULL;
    return new_head;
 
}
 
Node * reverse_recursion_version(Node * head)
{
    if(head->next==NULL)
    {
        return head;
    }
    Node *tmp,*new_head;
    tmp=head->next;
    new_head=reverse_recursion_version(tmp);
    tmp->next=head;
    head->next=NULL;
    return new_head;
}
int main()
{
    Node * head=NULL;
    cout << "this is normal order" << endl;
    head=creat_link();
    show_display_link(head);
    cout <<"this is reverse order"<<endl;
    //head=reverse_iteration_version(head);
    //head=reverse_iteration_version(head);
    head=reverse_recursion_version(head);
    show_display_link(head);
    return 0;
}

内容总结

以上是互联网集市为您收集整理的递归，迭代，堆栈三种方式实现单链表反转（C++）全部内容，希望文章能够帮你解决递归，迭代，堆栈三种方式实现单链表反转（C++）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端