[力扣] 剑指 Offer 第二天 - 反转链表
耐心和持久胜过激烈和狂热。
题目来源
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目描述
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例
题目分析
第一种做法是使用递归,递归到尾结点时,回溯,将每个节点的 next 指向反转,此时的尾结点就是反转后的头结点。第二种做法是迭代法,也就是双指针法,通过两个指针改变每个节点的指向。
解题思路
递归
链表 n1 → n2 → ··· → nk-1 → nk → nk+1 → nm
若想将 nk+1
的下一个节点指向 nk
,做法是 nk.next.next = nk
,简单解释一下这行代码,nk.next
等于 nk+1
,而 nk.next.next
= nk+1.next
→ nk
,这样就实现了反转,特别注意的是,需要将某个节点的下一个节点指向空(n.next = null
),避免回环,也能达到将尾结点指向空的目的。递归的终止条件是当前节点为空或当前节点的下一个节点为空,反转操作在回溯阶段进行。
迭代(双指针)
遍历链表,在遍历的过程中修改节点的指向,由于需要指向前节点,因此需要定义一个指针,用于保存前节点,改变指向之后,就会造成原本的下一个节点无法找到,因此还需要定义另一个指针,再改变指向之前,保存下一个节点。
代码实现
递归
执行结果
复杂度分析
时间复杂度:O(N),N 为 链表的长度,递归需要遍历链表一次。空间复杂度:O(N),递归需要 O(N) 的栈空间。
迭代
代码实现
执行结果
复杂度分析
时间复杂度:O(N),N 为链表的长度,需要遍历链表一次。空间复杂度:O(1),没有使用额外的内存空间。
总结
根据执行结果可以看出,递归比非递归慢,原因是每次分配函数内存以及栈都需要时间。
以上是本人的解法,如果对你有帮助,欢迎点赞收藏加关注,如果有错误的地方,欢迎指正!
版权声明: 本文为 InfoQ 作者【陈明勇】的原创文章。
原文链接:【http://xie.infoq.cn/article/e0c6da266bf21d49bc2c0648f】。文章转载请联系作者。
评论