菜狗开始重新读一遍数据结构啦，找找自己还不会的算法做做，今天从第二章看起，看到一款算法——逆转一个线性链表。这个仿佛需要思考一会，算法设计的也比较巧妙。
开心上代码：
#include <iostream> using namespace std; //创建一个链表节点 typedef struct linkNode { struct linkNode *link; int data; }*linkList; int main() { //创建一个链表 linkList p,r,list=NULL; int a[5]={1,2,3,4,5}; for(int i=0;i<5;i++) { p=new linkNode; p->data=a[i]; p->link=NULL; if(NULL==list) { list=p; } else { r->link=p; } r=p;//把p永远放在链表最后 } // linkList y; // y=list; // while(y!=NULL) // { // cout<<y->data<<" "; // y=y->link; // } //来逆转它 linkList q,s,t;//需要三个辅助变量 q=list; s=NULL; while(q!=NULL) { //依次给它们轮转赋值，q在依次往后迁移 //每一次循环，都断开下一个link指针，并将其指向原有的前驱节点 t=s; s=q; q=q->link; s->link=t; } //逆转完毕后，链表现在的首节点是s list=s; // linkList z; // z=list; // while(z!=NULL) // { // cout<<z->data<<" "; // z=z->link; // } return 0; }
