牛客网 BM1 反转链表

题目描述

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

思路分析

这里我们需要定义3个指针（命名为pre，cur，nex），下面解释一下三个指针分别的作用。

pre：用于指向已经完成反转的链表的头节点，最开始指向null。

cur：指向链表的当前对应节点，最开始指向头节点

nex：指向当前节点的下一个节点。

流程：

从头节点开始，将cur->next指向pre，随后将cur指针赋给pre，相当于让pre指向的cur当前的节点，之后再将nex的值赋给cur实现遍历的作用，直到cur为NULL，返回pre即可。

图示

完整代码

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