算法1(迭代)

解题思路

1. 定义3个指针变量，cur表示当前指向的节点，next表示cur翻转前指向的后继节点，prev表示翻转后cur指向的“后继结点”(也就是前驱节点)。
2. next指针一定要放在while()中，不然不能实时更新，会RE。
3. 逻辑：用next存储cur的后继cur->next，为了cur指针向后遍历而存在，使用next存储了cur->next的值以后，就可以实现翻转了，让cur->next指向prev，然后prev更新prev = cur，最后cur向后移动一格，用到了之前定义的next变量，cur = next。

代码

/**
 * 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 *cur = head;

        while(cur)
        {
            ListNode *next = cur->next;
            cur->next = prev, prev = cur, cur = next;
        }

        return prev;
    }
};

算法2(递归)

解题思路

1. 样例中是1 2 3 4 5，从2为头结点开始递归，调用reversList()函数，得到5 4 3 2
2. 此时的链表并不是1 5 4 3 2，这样想是错的，此时的链表是1->2和5 4 3 2，也就是头结点1依然指向的是2，只不过2现在是新链表(以tail 5为头结点的链表)的尾节点了，想要访问到2，就使用head->next就可以。
3. 让2指向1，让1指向NULL，就可以实现翻转。head->next->next = head, head->next = null，二者顺序不可调换，不然会提前更新1的后继节点，会错。

代码

/**
 * 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;
        ListNode *tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;

        return tail;
    }
};