单链表的逆置的实现:

(1)算法

struct link
{
   int data;
   struct link *next;
};

link reverse(link x)
{
   if( NULL==x )
     return NULL;
  
   link t=NULL;
   link r=NULL, y=x;   //(0)
   while(y!=NULL)
   {
     t = y->next;    //(1)
     y->next = r;    //(2)
     r = y;          //(3)
     y = t;          //(4)
    }

   return r;      //返回逆置后的链表
}

(二)原理
(0)(1)(2)(3)(4)分别对应以上程序的各序号
第一次while循环
-------------------------------------------
(0) r=NULL, y=x

r=NULL     a     --->     b      --->    c    --->   d --> NULL
                |(0)            
                y            

-------------------------------------------
(1) t =y->next

r=NULL     a     --->     b      --->    c    --->   d --> NULL
               |(0)             | (1)  
                y                 t


--------------------------------------------
(2) y->next = r
              
a     --->   NULL             b      --->    c    --->   d --> NULL
|(0)      (2)   |                  | (1)  
y                 r                   t

---------------------------------------------       
(3) r = y    
          
a     --->   NULL             b      --->    c    --->   d --> NULL
|(0)    (2)                      | (1)  
y                                   t
|(3)
r

---------------------------------------------
(4) y = t
              
a     --->   NULL             b      --->    c    --->   d --> NULL
|(0)    (2)                       | (1)  
|                                    t
|(3)                              | (4)
r                                     y


第二次while循环(并对上面进行整理)
---------------------------------------------
(1) t = y->next
              
a     --->   NULL             b      --->    c    --->   d --> NULL
|                                 |               |(1)
r                                    y                t
                         
---------------------------------------------
(2) y->next = r
              
b   --->   a     --->   NULL          c    --->   d --> NULL
|   (2)      |                                 |(1)
y             r                               t

---------------------------------------------
(3) r = y
              
b   --->   a     --->   NULL          c    --->   d --> NULL
|   (2)                                        |(1)
y                                                t
|   (3)
r

---------------------------------------------
(4) y = t
              
b   --->   a     --->   NULL          c    --->   d --> NULL
|   (2)                                       |(1)
|                                                t
|   (3)                                        |(4)
r                                                y


第三个循环 (并对上面的进行整理)
---------------------------------------------
(1) t = y->next
              
b   --->   a     --->   NULL          c    --->   d --> NULL
|                                                |             |(1)
r                                               y            t

以后的与第二次循环同, 最终可得:
              
d ---> c   ---> b   --->   a     --->   NULL

#include<iostream.h>
//using namespace std;

struct List //定义一个全局结构
{
    int ID;
    char name[10];
    int score;
    List *next;
    };
   
    List *head;     //定义链表头
   
    List* creat()    //开始创建链表
    {
    List* ps;
    List* pend;
    ps=new List;//定义一个动态的指针，便于输入新的数据
    cout<<"输入学号 姓名 成绩："<<endl;
    cin>>ps->ID>>ps->name>>ps->score;
    head=NULL;//开始设表头指向空地址
    pend=ps;//让临时指针等于新输入指针的地址，其实别个喜欢把他说成是链尾指针，我觉得非常不恰当也，其实就是一个临时地址便于赋值阿。
    while(ps->ID!=0)
    {
        if(head==NULL)
            head=ps;//第一次循环
            else
                pend->next=ps;//这里就可以看到为什么要用pend这个临时地址的原因了，就是为了和下一个地址串联起来，下一句也是这个道理
               
                pend=ps;//这里刚开始看得的时候有点不明白，其实主要是相对于第一次循环来说它连续赋值两次，但是后面的循环这个就太重要了
                ps=new List;
    cin>>ps->ID>>ps->name>>ps->score;
        }
        pend->next=NULL;
//    pend->next=head;//若要变成单循环链表，改这一句就够了
        delete ps;
        return (head);
        }

void display(List* p)
{
    if(p==NULL)
        {
            cout<<"空链表"<<endl;
        return;
    }
    cout<<"输出链表："<<endl;
    while(p)
    {
    cout<<p->ID<<" "<<p->name<<" "<<p->score<<endl;
    p=p->next;
    }
}

       
List *reverse(List *&h)
{
List* q=h;
List *t=NULL;
List *y=NULL;
while(q)
{
   t=q->next;
   q->next=y;
   y=q;
   q=t;
   }
  
   return y;
}
int main()
{

    head=creat();

    cout<<"链表逆置："<<endl;
   
    display(reverse(head));
   
    return 0;
    }