牛客网 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即可。
图示
完整代码
代码语言：javascript复制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;
}
