【刷题】反转链表 2种解法:迭代&递归 对比分析

简介: 【刷题】反转链表 2种解法:迭代&递归 对比分析

题目描述


给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。


示例


示例 1:


微信图片_20221112165137.jpg


输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

微信图片_20221112165141.jpg


输入: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
}


运行结果

微信图片_20221112165144.jpg


递归解法


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
}


运行结果


微信图片_20221112165147.jpg


总结


通过运行结果我们可以很清晰的看到:迭代比递归更节省内存,在执行时间方面表现一致,两者的时间复杂度都是O(n),n是链表的长度。


相关文章
|
3月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
3月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
33 0
|
3月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
27 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3月前
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
54 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4
|
3月前
|
存储 Python
【Leetcode刷题Python】23. 合并K个升序链表
合并K个升序链表的方法:使用数组排序的暴力求解法、使用小顶堆的高效方法,以及分而治之的策略,并提供了相应的Python实现代码。
19 1
|
3月前
|
机器学习/深度学习
【刷题记录】相交链表
【刷题记录】相交链表
|
3月前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0