单向链表翻转实现

  • A+
所属分类:编程开发

链表管理会用到指针,指针是非常灵活的数据结构,但也容易掉坑里。
翻转链表,主要是要考虑好它的结构。可以画图来帮助思考。然后就是注意一些变量的变化。

#include <string>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long

struct node{
       int x;
       node *next;
};
//输出
int printlist(node *ps){
    while(ps!=NULL){
       printf("%d %d %d\n",ps,ps->x,ps->next);
       ps=ps->next;
    }
    return 0;
}
//翻转
node *overturn(node *start){
         //开始反转
    node *ps=start;
    node *tmp=NULL;
    node *last=NULL;
    while(ps!=NULL){
        //保存原链表中,这个节点指向的下一个节点。
        tmp=ps->next;
        //将当前节点指向上一个节点
        ps->next=last;
        last=ps;       
        ps=tmp;
    }
    start=last;
    return start;
}

node *init(){
    node *start=NULL;
    node *last=NULL;
    node *ps=start;
    int x,num;
    scanf("%d",&num);
    for(int i=0;i<num;i++){
        scanf("%d",&x);
        node *ps=new node;

        //链表赋值
        ps->x=x;
        ps->next=NULL;

        //让上一个指针向它
        if(last==NULL){   
            start=ps;
        }else{
            last->next=ps;
        }
        last=ps;
    }
    return start;
}

int deletelist(node *ps){
    node *tmp;
    while(ps!=NULL){
       tmp=ps;
       ps=ps->next;
       delete tmp;
    }
}

int main(void)
{
    //数据输入
    node * start=init();
    //输出链
    printlist(start);
    //分割线
    printf("\n");
    //翻转
    start= overturn(start);
    //输出链
    printlist(start);
    //回收内存
    deletelist(start);
    start=NULL;
    return 0;
}

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: