题目描述： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题目OJ链接： link

解题思路：

方法一
使用三个指针 pre、cur 和 next 它们的初值分别为 NULL、head 和 head->next。然后让 cur->next = pre 产生逆序，接着三个指针都往后走一步，继续逆序，直到 cur == NULL 。此时 pre 就是逆置后链表的头节点，返回 pre 即可。

代码如下：

typedef struct ListNode ListNode;

struct ListNode* reverseList(struct ListNode* head) {
    
    // 空表或者一个节点
    if (NULL == head || NULL == head->next)
        return head;

    // 至少两个节点
    ListNode* pre = NULL;
    ListNode* cur = head;
    while (cur)
    {
        // 存储下一个节点的位置
        ListNode* next = cur->next;
        // 逆置当前节点
        cur->next = pre;
        // 下一组
        pre = cur;
        cur = next;
    }
    // 返回逆置链表头节点
    return pre;

}

方法二
使用一个函数 reverse_list() 进行递归来完成，该函数的函数原型如下：

void reverse_list(ListNode* pre, ListNode* cur);

是用该方法需要提前存储尾节点作为逆置链表的头节点返回。

代码如下：

typedef struct ListNode ListNode;

void reverse_list(ListNode* pre, ListNode* cur)
{
    if (cur)
    {
        // 下一层递归
        reverse_list(cur, cur->next);
        // 逆序
        cur->next = pre;
    }
}

struct ListNode* reverseList(struct ListNode* head) {
    // 空表或者一个节点
    if (NULL == head || NULL == head->next)
        return head;
    // 存储尾节点
    ListNode* tail = head;
    while (tail->next)
        tail = tail->next;
    // 递归
    ListNode* pre = NULL;
    ListNode* cur = head;
    reverse_list(pre, cur);
    // 返回逆置链表头节点
    return tail;
}