这道题是在面试时遇到的，要求实现链表反转的递归版，这道题其实思想非常的简单，而且几行代码就可以实现，但是在面试时出现，这的确如果之前练习的是非递归版的链表反转实现，那么来一个递归版的，可能需要花点时间来适应一下。
以下实现了两个版本的递归版单链表反转，这道题从两个角度看，区别在于，递归调用的返回值是什么，如果递归调用的返回值是输入结点，那么直接在这一层函数连接当前结点，另一个是在下一层调用中完成链表的反转。
// 结点的定义
struct Node { int value; Node* next; Node(int val) : value(val) {} };
// 传统的方法，在递归调用的下一层完成链表的反转：
class Solution { public: // 递归版链表反转 Node* reverseList(Node* node) { if (node == NULL || node->next == NULL) return node; Node* tmp = node->next; node->next = NULL; return reverse_list(node, tmp); } Node* reverse_list(Node* node1, Node* node2) { if (node2 == NULL) return node1; Node* tmp = node2->next; node2->next = node1; return reverse_list(node2, tmp); }
}；
Node* lastnode = NULL;
class Solution{
public:
// 另一种递归递归完成链表反转 void reverseList(Node* node) { if (node == NULL || node->next == NULL) { lastnode = node; return; } reverse_list(node->next)->next = node; node->next = NULL; } Node* reverse_list(Node* node) { if (node->next == NULL) { lastnode = node; return node; } reverse_list(node->next)->next = node; return node; }
};
int main() { Solution s; Node* node = new Node(0); Node* tmp = node; for (int i = 1; i < 3; i++) { tmp->next = new Node(i); tmp = tmp->next; } tmp->next = NULL; s.reverseList(node); for (int i = 0; i < 3; i++) { tmp = lastnode; lastnode = lastnode->next; delete tmp; } return 0; }
