反转链表-递归反转法

（1）思想：和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。
（2）实现（建议先看代码，再看图解，使理解更加深刻）：

开始递归：

        new_head经过三次函数递归的调用来到了链表的最后一个结点，因为new_head=head->next,所以head始终保持在new_head的前一个结点处。

递归到最后一层时： 

 开始逐层出递归：

 

 

 

递归结束。

最后的结果为：

 

代码片段：

link* recursive_reverse(link* head) {
	//出递归条件 
    if (head == NULL || head->next == NULL)    
    {
        return head;
    }
    else
    {
    	//new_head一直找到链表中的最后一个元素的地址 
        link *new_head = recursive_reverse(head->next);
        //出递归后，将链表 
        head->next->next = head;
        head->next = NULL;
        return new_head;
    }
}

完整代码：

#include<stdio.h>
#include<stdlib.h>

typedef struct Link{
	int elem;
	struct Link* next;
}link;

link* initLink(){
	int i; 
	//定义头指针 
	link* head=NULL;
	//定义首元结点
	link* temp=(link*)malloc(sizeof(link));
	//首元结点初始化
	temp->elem=1;
	temp->next=NULL;
	head=temp;
	//创建其他结点
	for(i=2;i<5;i++){
		link* a=(link*)malloc(sizeof(link));
		a->elem=i;
		a->next=NULL;
		temp->next=a;
		temp=temp->next; 
	} 
	//返回头指针的地址 
	return head;
}

void printLink(link* head){
	link* p=head;
	while(p){
		printf("%d ",p->elem);
		p=p->next;
	}
	printf("\n");
}

link* recursive_reverse(link* head) {
	//出递归条件 
    if (head == NULL || head->next == NULL)    
    {
        return head;
    }
    else
    {
    	//new_head一直找到链表中的最后一个元素的地址 
        link *new_head = recursive_reverse(head->next);
        //出递归后，将链表 
        head->next->next = head;
        head->next = NULL;
        return new_head;
    }
}

int main()
{
	link*p=initLink();
	printf("原始链表：");
	printLink(p);
	printf("反转链表：");
	p=recursive_reverse(p); 
	printLink(p);
	return 0;
} 

输出结果：