题目要求：

题目链接：点击这里，直接跳转

思路：

方法1：头插法
将链表每个节点依次取下来头插到新链表，即为原链表的反转；因为改变了当前节点的 next 指向，必须先保存 next 地址。

图解如下：

重复以上步骤：直到终止循环

实现代码：

struct ListNode* reverseList(struct ListNode* head){
    //新链表的头指针
    struct ListNode* newhead = NULL;
    //需要头插的结点
    struct ListNode* cur = head;
    
    while(cur)
    {
        //保存需要头插结点的下一个节点
        struct ListNode* next = cur->next;
        //将cur头插到新链表
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

方法2：迭代

假设存在链表 1→2→3→∅，我们想要把它改成 ∅←1←2←3

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用。

图解如下：

实现代码：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* pre = NULL;
    //需要反转指向的结点
    struct ListNode* cur = head;
    
    while(cur)
    {
        //保存需要头插结点的下一个节点
        struct ListNode* next = cur->next;
        //将cur头插到新链表
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}