Reverse a singly linked list.

思路：递归，每次保存一下上一个节点用来构造反转后的链表。

非递归，需要多记录两个值.

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* ans = nullptr;    void dfs(ListNode* p, ListNode* q) {        if (p == nullptr) {            ans = q;            return ;        }        dfs(p->next, p);        p->next = q;        if (q) q->next = nullptr;    }     ListNode* reverseList(ListNode* head) {        dfs(head, nullptr);        return ans;    }};

/** * 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) {        ListNode *prev = NULL;        ListNode *next = NULL;        while (head) {            next = head->next;            head->next = prev;            prev = head;            head = next;        }        return prev;    }};