LeetCode 206 - 反转链表

这篇具有很好参考价值的文章主要介绍了LeetCode 206 - 反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode 206 - 反转链表

题目描述

给定一个单链表的头节点 head,反转该链表并返回反转后的链表。

解题思路

我们可以使用迭代或递归的方式来反转链表。文章来源地址https://www.toymoban.com/news/detail-792022.html

迭代法

  1. 初始化三个指针 curprenext
  2. 遍历链表,将 cur.next 指向 pre,然后将 precur 向前移动一步。
  3. 重复上述步骤,直到 cur 到达链表末尾。

递归法

  1. 递归到链表末尾,返回链表末尾节点。
  2. 在递归的回溯过程中,将当前节点的 next 指针指向当前节点,并将当前节点的 next 置空。
  3. 最终返回新的头节点。

解法示例

迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

递归法

class Solution {
    public ListNode reverseList(ListNode head) {
       if (head == null || head.next == null) {
           return head;
       }
       ListNode newHead = reverseList(head.next);
       head.next.next = head;
       head.next = null;
       return newHead;
    }
}

复杂度分析

迭代法

  • 时间复杂度:O(n),其中 n 是链表的长度。
  • 空间复杂度:O(1)。

递归法

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n),递归调用栈的深度。

到了这里,关于LeetCode 206 - 反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 206. 反转链表、Leetcode的Python实现

    博客主页:🏆 看看是李XX还是李歘歘  🏆 🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺 💗 点关注不迷路,总有一些📖知识点📖是你想要的 💗 ⛽️今天的内容是      Leetcode    206. 反转链表     ⛽️💻💻💻 206. 反转链表 给你单链表的头节点 

    2024年02月06日
    浏览(35)
  • 力扣每日一道系列 --- LeetCode 206. 反转链表

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 206. 反转链表 初始化两个指针, cur 和 newhead 。 cur 指向给定的链表头节点, newhead 初始为 NULL 。 在 cur 不为空的情况下,执行循环。 首先,记录下 cur 的下

    2024年02月04日
    浏览(38)
  • 刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

    本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解 参与链接在此 : https://programmercarl.com/other/xunlianying.html 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个

    2023年04月09日
    浏览(50)
  • 代码随想录第三天|链表理论基础,LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表

    链表: 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是head。 链表类型: 1.单链表 单链表中的指

    2024年02月11日
    浏览(49)
  • 【Leetcode60天带刷】day03链表——203. 移除链表元素,707.设计链表,206. 反转链表

    链表就像一串小火车,有一节一节的车厢,每个车厢都叫做一个节点。  单链表:每个链表车厢里有两个内容,一个放的是真正的数据,另一个放的是下一节车厢的编号。 双链表:每个链表车厢里有三个内容,一个真正数据,一个下一个车厢的编号,还有一个上一节车厢的编

    2024年02月06日
    浏览(48)
  • 【LeetCode题目详解】 203. 移除链表元素707. 设计链表206. 反转链表 day3(补)

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 看到这道题就想到了链表 这道题有两种写法,涉及如下链表操作的两种方式: 直接使用

    2024年02月16日
    浏览(41)
  • 算法leetcode|92. 反转链表 II(rust重拳出击)

    给你单链表的头指针 head 和两个整数 left 和 right ,其中 left = right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 链表中节点数目为 n 1 = n = 500 -500 = Node.val = 500 1 = left = right = n 你可以使用一趟扫描完成反转吗? 将链表分成3部分,即前面不需要反转的部

    2024年02月05日
    浏览(49)
  • 算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表

    题目链接:力扣 思路:删除链表元素与数组不同之处在于,它需要被删除链表元素的前一个元素和后一个元素的参与,而不需要其他元素的参与。 我们使被删除元素前一个元素的指针指向被删除元素的后一个元素 ,也就是直接跳过被删除的元素,来实现删除。 同时我们考

    2024年02月05日
    浏览(38)
  • 代码随想录Day3 | 链表01-leetcode203、707、206

    题目链接:移除链表元素 思路: 链表中元素的添加和删除关键是要 保证不断链且指向关系正确 。对于删除操作,链的修改涉及将待删除元素的前一个元素指向待删除元素的后一个元素,因此在判断当前元素是否需要删除时,要记录当前元素的前后指针。 1.删除头结点时另作

    2024年02月16日
    浏览(63)
  • 【Leetcode】重排链表、旋转链表、反转链表||

    目录 💡重排链表 题目描述 方法一: 方法二: 💡旋转链表 题目描述 方法: 💡反转链表|| 题目描述 方法: 💡总结 给定一个单链表  L   的头节点  head  ,单链表  L  表示为:  L0 → L1 → … → Ln-1 → Ln  请将其重新排列后变为: L0 → Ln → L1 → Ln-1 → L2 → 

    2024年02月03日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包