题解 | 反转链表（递归法）

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        // write code here
        //如果只有一个或者开头就为空，那就直接返回这个东西为新头节点
        if(head==nullptr||head->next==nullptr)
            return head;
        //标记一下下一个，返回值是反的链表，要找最末尾的位置加上当前的节点，如果用新头找会遍历，太慢
        ListNode* nxt = head->next;
        //递归的思路就是能有下一个就找下一个，返回值是下一个及以后的所有节点构成的链表
        ListNode* ans = ReverseList(nxt);
        //给这个链表加上当前节点
        nxt->next = head;
        //这个节点是目前的尾巴，为了考虑最后一个尾巴的情况，所以所有的目前尾巴的下一位都置为空指针
        head->next = nullptr;
        //因为返回的是新链表头，本节点只是多加了一个尾巴，还是要返回后面节点带来的链表的新头指针
        return ans;
    }
};