C代碼
/**
*鏈表逆序的遞歸/非遞歸算法
*/
#include <stdio.h>
typedef int Item;
typedef struct node
{
Item item;
struct node *next;
}Node, *List;
/*reverse1~2是不帶頭結點的逆序算法*/
List reverse1(List l)
{
Node *p1,*p2;
if(l==NULL)
return l;
p1=l->next;
l->next=NULL;
while(p1!=NULL){
p2=p1->next;
p1->next=l;
l=p1;
p1=p2;
}
return l;
}
List reverse2(List l)
{
if(l==NULL || l->next==NULL)
return l;
Node *p=reverse2(l->next);
l->next->next=l;
l->next=NULL;
return p;
}
/*reverse3~4是帶頭結點鏈表的逆序算法*/
void reverse3(List l)
{
Node *p1,*p2,*p3;
if(l==NULL || l->next==NULL)
return;
p1=l->next;
p2=p1->next;
p1->next=NULL;
while(p2!=NULL){
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
l->next=p1;
}
void reverse4(List l, Node *first)/*此算法不是很好，需要在函數外判斷l!=NULL*/
{
if(first==NULL || first->next==NULL){
l->next=first;
return;
}
reverse4(l,first->next);
first->next->next=first;
first->next=NULL;
}
作者“Ackerman's Blog”
