递归方法的常用步骤：
1. 生成子问题。
子问题须与原始问题为同样的事，且更为简单。即把N的问题简化到N-1；
2. 构造出口。
不能无限制地调用本身，须有个出口，化简为非递归状况处理。即当N==某个值时可解。
首先，我们实现从N到N-1：
对于链表A->B->C->D->NULL，我们对后面的B->C->D->NULL 进行逆序： D->C->B->NULL
然后我们在B后插入A：D->C->B->A->NULL
代码：
Node* reversalList(Node* pHead) { //对后面的节点进行逆序 Node* nowHead = reversalList(pHead->mpNext); //在新链表的最后插入原头结点 Node* pNode = nowHead; while (pNode->mpNext) { pNode = pNode->mpNext; } pHead->mpNext = pNode->mpNext; pNode->mpNext = pHead; return nowHead; }
接着，我们实现出口：
当链表只有两个节点时，直接交换两个节点即实现链表的逆序。
代码：
Node* reversalTwo(Node* pHead) { Node* pNode = pHead; pHead = pHead->mpNext; pNode->mpNext = pHead->mpNext; pHead->mpNext = pNode; return pHead; } //如果只有两个节点则直接交换 if(pHead->mpNext->mpNext == NULL) { return reversalTwo(pHead); }
完整的实现过程：
#include <iostream> struct Node { int mVal; Node* mpNext; }; void addNode(Node* pHead, int val) { if(NULL == pHead) return; Node* pNode = new Node; pNode->mVal = val; pNode->mpNext = pHead->mpNext; pHead->mpNext = pNode; } Node* createList() { Node* pHead = new Node; pHead->mVal = 0; pHead->mpNext = NULL; return pHead; } Node* reversalTwo(Node* pHead) { Node* pNode = pHead; pHead = pHead->mpNext; pNode->mpNext = pHead->mpNext; pHead->mpNext = pNode; return pHead; } Node* reversalList(Node* pHead) { if(pHead->mpNext->mpNext == NULL) { return reversalTwo(pHead); } Node* nowHead = reversalList(pHead->mpNext); Node* pNode = nowHead; while (pNode->mpNext) { pNode = pNode->mpNext; } pHead->mpNext = pNode->mpNext; pNode->mpNext = pHead; return nowHead; } void main() { Node* pHead = createList(); addNode(pHead, 1); addNode(pHead, 2); addNode(pHead, 3); Node* nowHead = reversalList(pHead->mpNext);//因为createList返回的头结点并没有保存有用数值，所以首节点用头结点的next； return;
}