反转链表（链表的逆置）

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例：

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

方法一：头插法

 每次把结点p头插，结点p从head（头结点）的下一个结点开始直到尾结点结束。

头插结束后链表结点逆置。

struct ListNode* reverseList(struct ListNode* head){

    struct ListNode*p=head->next;

    struct ListNode*q=p->next;

    while(p!=NULL)

    {

        q=p->next;

        p->next=head->next;

        head->next=p;

        p=q;

    }

    return head;

}

方法二：制代法

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

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*pre=NULL;
    struct ListNode*cur=head;
    while(cur!=NULL)
    {
        struct ListNode*next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return pre;
}