题目描述
给你单链表的头节点 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代码
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代码
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是链表的长度。