看动画，拿 Offer：大厂算法面试真题全解析

添加社群管理员：微信号【】
订阅福利订阅后，分享专属海报，每邀请一位好友订阅有奖励。免费获取价值 800 元大礼包最新课表抢先看，订阅会员更优惠。找客服要优惠：微信号【】链表逆序（ 206）
今天讲解的题目选自206 链表逆序
题目
已知一个单链表，头结点指针为 head ，我们需要将 head 指向的链表进行逆序，并返回逆序后的头结点地址。
例如，链表中存储了 1、2、3、4、5 这 5 个结点，逆序后变为 5、4、3、2、1 ，此时头结点中存储了 5 ，将它返回。
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
这里我们要注意，解决该问题需要在原链表上进行相关操作，不可以申请类似数组的额外内存空间，保证空间复杂度为 O(1) 。
题目中节点的数据结构，代表链表中的一个节点， val 是节点中存储的数据， next 是指向下一个节点的指针，构造函数初始化 val 的值为 x ， next 赋为空。
我们需要实现函数，函数传入原链表的头结点指针 head ，返回逆置后的新链表头结点地址。例如，输入链表 1、2、3、4、5 ，返回逆置后链表头结点 5 的地址。
我们首先思考如何将链表一个结点一个结点的逆置。
先看一段打印链表的代码，，函数传入两个参数，链表的头结点指针 head 和链表的名字 name 。在函数中，打印字符串 name 。然后判断 head 是否为空，如果 head 为空，打印 NULL ，并返回。如果 head 不空，遍历并打印链表的每一个节点值。
接着我们开发主程序，首先构造 5 个结点 a、b、c、d、e ，并将它们初始化为 1、2、3、4、5 ，通过结点的 next 指针域，将 a、b、c、d、e 这 5 个结点依次连接在一起。
下面我们来研究如何将链表一个结点一个结点的逆置。
设置 head 指向链表的头结点 a ，设置为新链表头结点指针，最初指向空。
设置指针 next ，初始化为空，后面 next 用来备份当前操作结点的下一个结点的地址。
我们调用函数，打印出当前 head 与指向的链表。我们发现旧链表打印结果为 1、2、3、4、5 ，新链表打印结果为 NULL 。
然后对第一个结点逆置，逆置结点包括 4 个步骤。
首先通过代码 next = head->next (读作 next 等于 head next) ，备份 head 的下一个结点的地址。
【看动画，拿 Offer：大厂算法面试真题全解析】然后通过代码 head->next =将 head 的指针域赋值为，即将第 1 个结点与原链表断开，使它指向新链表的头结点。
接下来把指向新链表的头结点，通过代码= head ，将赋值为 head 。
最后通过代码 head = next ，将 head 指向当前原链表的头结点。
至此，我们完成了一个节点的逆置。调用打印出原链表与新链表， head 对应的原链表为 2、3、4、5 ，对应的新链表为 1 。
我们再来看第二个结点的逆置。和第一个节点逆置的过程相同，首先通过代码 next = head->next ，备份 head 指针的下一个节点地址，将它存储至 next 中。
然后通过代码 head->next = ，将第 2 个结点与原链表断开，使它指向新链表的头结点。