c语言逆置单链表

/*

*this is a program to reverse a list

*by beibei

*/

 

#include
#include

 

//定义节点，测试方便，只定义了一个整形。

typedef struct INode{
  int data;
  struct INode* next;
}Node;

 

//新建链表函数

Node* newList(int n)
{
  Node *List=NULL;
  Node *tmp;
  int i;
  for(i = 0;i < n;i++){
    tmp = (Node *)malloc(sizeof(Node));
    tmp->data = i;
    tmp->next = List;
    List = tmp;
  }
  return List;
}

 

//释放内存

void freeList(Node* List)
{
  Node *next,*tmp;
  for(tmp = List;tmp != NULL;tmp = next){
    next=tmp->next;
    free(tmp);
  }
}

 

//打印链表

void printList(Node* List)
{
  Node* pr = List;
  while(pr!=NULL){   
    printf("%d ",pr->data);
    pr = pr->next;
  }
  printf("\n");
}

 

//循环方式逆置（标准）

Node* reverse1(Node* List)
{
  Node *pre=NULL;
  Node *next=NULL;
 
  while(List!=NULL){
    next=List->next;
    List->next=pre;
    pre = List;
    List = next;
  }
  return pre;
}

 

//递归方式

Node* reverse2(Node* List)
{
    Node *tail;

    if (NULL == List || NULL == List->next)
        return List;
  
    tail = reverse2(List->next);
    List->next->next = List;
    List->next = NULL;

    return tail;
}

 

//简单的测试

int main()
{
  Node* ListTest=newList(6);
  printList(ListTest);
//  freeList(ListTest);
//  printList(ListTest);
  Node* res=reverse2(ListTest);
  printList(res);
  return 0;
}