笔试链表题（牛课网笔试题101BM1反转链表）

笔试链表题（牛课网笔试题101BM1反转链表）快手 百度 蘑菇街二 关联企业经反转后，原链表变为{3 2 1}，所以对应的输出为{3 2 1}。以上转换过程如下图所示：示意图

一 题目描述

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

数据范围： 0\leq n\leq10000≤n≤1000

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

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

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

以上转换过程如下图所示：

示意图

二 关联企业

快手 百度 蘑菇街

三 代码方案

1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr
2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head
3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
接下来，循环执行以下三个操作
1）nex = cur->next 保存作用
2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点
循环条件，当然是cur != nullptr
循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点
这里以1->2->3->4->5 举例：

class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode *pre = nullptr; ListNode *cur = pHead; ListNode *nex = nullptr; while (cur) { nex = cur->next; cur->next = pre; pre = cur; cur = nex; } return pre; } };