倒置链表：递归代码在最后
实现方式（这里只有递归的，其他的实现方式在我其他文章里）
1. 尾插
思想就是遍历到链表尾然后从头指针拆地址插到尾的下一个，指向空，头指针一直向下移动，直到下移到尾，返回尾指针。
2. 首插
三指针移动，一直利用三个指针保存当前节点上一个和下一个节点以及当前节点，当前节点指向前一个节点，然后整体指针右移动，直到下一个节点到达空。
3. 递归
分析：递归就是为了解决重复问题，从后往前分析，假设后面已经完成了所有的工作，只需要分析当前状态即可。只要所有动作都是重复的而且依赖于前一个的完成，就能用递归。
要用递归必须考虑三个方面：
出口：即结束条件
重复：所有的操作都是一样的
返回值：递归需要返回什么吗
仔细分析发现首插，就满足递归，每次都是定义三个指针，完成保存，断开，连接，后移。
这个是从前往后走然后直接得到尾节点即可。递归是从后往前走，因此要想得到倒置链表，
首先必须得到尾部节点的地址，因此得出出后和返回值。大体架构得出。
RecursionReverseList(List *pHead)
if(pHead == NULL || pHead->pNext == NULL)return pHead;//得到最后的节点才返回
//以下两部分就是保证最后的节点被返回，每次递归回溯得时候都带着尾部地址
List *pNewHead = RecursionReverseList(pHead->pNext);
return pNewHead;
递归的结束和返回两个部分解决完
剩下的就是重复得地方：
分析递归时候我们有的情况：我们有当前位置和当前位置的下一个地址，回溯的时候会得到当前位置的上一个地址，
神奇发现，满足三指针（一个保存当前节点的前一个pProv，一个当前节点pNode，一个后一个节点pNext）
三指针作用pProv保存倒置链表的头，pNode原链表的头，pNext保存原链表下一个地址，
因为当前节点要接到倒置链表上，因此映射一下，pHead当前节点，pHead->pNext当前节点的下一个节点，
回溯后的pHead是前一个节点，正好是三指针的反向，pProv是原链表的下一个（要做原链表的头），
pNode是原链表的“头”，要接在倒置链表上,pNext是倒置链表的头，
因此连接的方式为pHead->pNext->pNext = pHead;
最后需要注意一点，原链表的头也就是倒置链表的尾需要指向NULL，因此需要每次pHead->pNext->pNext = pHead;
后需要pHead->pNext = NULL,就是为了保证最后一个节点指向空。
递归核心代码
List *ReverseList(List *pHead)
{
List *pNewHead = NULL;
if(pHead == NULL || pHead->pNext == NULL)return pHead;
pNewHead = ReverseList(pHead->pNext);
if(pHead != NULL){
pHead->pNext->pNext = pHead;
pHead->pNext = NULL;
}
return pNewHead;
}
递归全部代码（包含测试用例）
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int nValue;
struct node *pNext;
}List,Node;
Node *GetNode(int nValue);
void AddNode(List **pHead, Node *pNode);
void Trverse(List *pHead);
List *ReverseList(List *pHead);
Node *GetNode(int nValue)
{
Node *pTemp = (Node *)malloc(sizeof(Node));
pTemp->nValue = nValue;
pTemp->pNext = NULL;
return pTemp;
}
void AddNode(List **pHead, Node *pNode)
{
if(pHead==NULL || pNode==NULL)return;
if(*pHead == NULL){
*pHead = pNode;
}else{
List *pTemp = *pHead;
while(pTemp->pNext){
pTemp = pTemp->pNext;
}
pTemp->pNext = pNode;
}
}
void Trverse(List *pHead)
{
if(pHead == NULL)return;
while(pHead){
printf("%d ",pHead->nValue);
pHead = pHead->pNext;
}
printf("\n");
}
List *ReverseList(List *pHead)
{
List *pNewHead = NULL;
if(pHead == NULL || pHead->pNext == NULL)return pHead;
pNewHead = ReverseList(pHead->pNext);
if(pHead != NULL){
pHead->pNext->pNext = pHead;
pHead->pNext = NULL;
}
return pNewHead;
}
int main()
{
List *pHead = NULL;
AddNode(&pHead, GetNode(1));
AddNode(&pHead, GetNode(2));
AddNode(&pHead, GetNode(3));
AddNode(&pHead, GetNode(4));
AddNode(&pHead, GetNode(5));
Trverse(pHead);
pHead = ReverseList(pHead);
Trverse(pHead);
return 0;
}
Processed:
0.011, SQL:
8
