链表逆转的几种方法

将单链表逆转
第一个版本：（程序如下，复杂但易懂）

Node * list_reverse(Node *head)
{
Node *cur;
Node *pre;
Node *next;
if(head==NULL) //链表没有节点。
return NULL;
pre=head;
cur=pre->link;
if(cur==NULL) //只有一个节点
return head;
else
next=cur->link;

head->link=NULL; //因为要作为尾节点。

if(next==NULL) //即只有两个节点的特殊情况。
{
    cur->link=pre;
    head=cur;
    return head;
}
while(next!=NULL)
    {
        cur->link=pre;
        pre=cur;
        cur=next;
        next=next->link;
    }
        cur->link=pre;
        head=cur;
        return head;
}*

第二版：（不需要三个指针，更简单，也不用考虑那么几种特殊情况）

Node * list_reverse(Node *head)
{
  Node * tmp=head;
  Node * next=head;
  if(head==NULL) //链表没有节点。
  return NULL;

  head=NULL; /// 此时head作为链表尾部了。
  //// 一下几步为：先存下当前节点tmp的下一节点用于备份，之后将tmp节点指向新链表的头部并且将新链表的头位置前移，同时控制每次循环都能指向后一个节点向前进行。
  while(tmp->link!=NULL)
  {
     next=tmp->link;
     tmp->link=head;
     head=tmp;
     tmp=next;
  }
  //// 循环退出的时候，tmp指向最后一个节点。
 tmp->link=head;
 head=tmp;
return tmp;
}

测试用例：

void main()
{
Node *root=list_creat( );
Node * pout=list_reverse(root);
list_show(pout);
list_destroy(pout);

结果：