题目
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
思考题：
请同时实现迭代版本和递归版本。
样例
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL

解法一：迭代

建立一个新的链表，头插法即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        auto h = new ListNode(-1), p = head;
        while (p) {
            auto q = p->next;
            p->next = h->next;
            h->next = p;
            p = q;
        }
        return h->next;
    }
};

解法二：递归

函数能做到每次将一段链表反转，我们这里只能选取head->next
那么经过递归后，返回的是已经反转的链表头，也就是原链表的最后一个结点
最后，我们需要让head->next指向head，head指向nullptr
注意递归的边界条件：head或者head->next为nullptr

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        auto h = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return h;
    }
};