如何实现一个单链表的反转?

wg0124

使用堆栈也需要消耗空间的，最起码要消耗如下的单元：
int i;    用于交换队列数据的空间。
链表 *p;  用于指向当前链表单元。
使用指针，需要消耗如下的空间：
链表 *p1,*p2,*p3;  其中p1，p3均用来指向当前处理的链表节点，p2用来指
                      向上个节点。
至于算法的复杂度我不是很清楚，我只知道使用堆栈要遍历(n-1)次链表，使用指针要遍历1次链表。
以下是俺测试用的使用指针的小程序，测试过（TC2.0）：
#include "stdio.h"

struct Link_Tab
{
  int dat;
  struct Link_Tab * next_nod;
}My_Link[5],*p,*q,*p1;

main()
{
  int i;

  //初始化链表（5节点）
  for(i=0;i<6;i++)
  {
    switch(i)
    {
      case 4:
        My_Link.dat=i;
        My_Link.next_nod=NULL;
        break;
      case 5:
        break;
      default:
        My_Link.dat=i;
        My_Link.next_nod=&My_Link[i+1];
        break;
    }
  }

//反序
  p=&My_Link[0];
  q=NULL;
  do
  {
    p1=(*p).next_nod;
    (*p).next_nod=q;
    q=p;
    p=p1;
  }while(p!=NULL);

//打印输出链表数据
  while(q!=NULL)
  {
    printf("%d\n",(*q).dat);
    q=(*q).next_nod;
  }

wg0124

如题           
!!!!!!!!!!