【刷题】反转链表 2种解法：迭代&递归 对比分析
Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。
春招打卡第19天第25篇。
勤学似春起之苗，不见其增，日有所长；辍学如磨刀之石，不见其损，日有所亏。
掘金的活动真多哇，这个月决定每天用go刷题，一方面提升一下算法水平，另一方面沉淀一下go语言的学习。
Let's GO!
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：
链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题思路
最近刷的这几道题都是链表的，异曲同工。
上面进阶提到了使用迭代或递归完成反转。心想不用这两种方式还能有其他方式么？！
为了让大家更好的刷题，下面介绍迭代和递归的区别：
迭代和递归
一、含义不同：
递归是重复调用函数自身实现循环，在递归循环中，遇到满足终止条件的情况时逐层返回来结束。
迭代则使用计数器结束循环。
二、结构不同：
递归与迭代都是基于控制结构：迭代用重复结构，而递归用选择结构。
递归与迭代都涉及终止测试：迭代在循环条件失败时终止，递归在遇到基本情况时终止。
迭代解法
AC代码
go
func reverseList(head *ListNode) *ListNode { var pre *ListNode cur := head for cur!= nil{ tmp := cur.Next cur.Next = pre pre = cur cur = tmp } return pre }运行结果
递归解法
AC代码
go
func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } newHead := reverseList(head.Next) head.Next.Next = head head.Next = nil return newHead }运行结果
总结
通过运行结果我们可以很清晰的看到：迭代比递归更节省内存，在执行时间方面表现一致，两者的时间复杂度都是O(n)，n是链表的长度。
来源说明
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/re…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最后
感谢阅读，欢迎大家三连：点赞、收藏、投币（关注）！！！