墨风如雪博客

  • 源码小店
  • 导航站
  • 登录
  • java
  • 资源分享
让AI使用变得如此简单
  1. 首页
  2. 算法
  3. 正文

每日算法题:反转链表

2023年 5月 16日 207点热度 0人点赞 0条评论

题目(反转链表)

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

例如,给定链表 1 -> 2 -> 3 -> 4 -> 5,反转后的链表应为 5 -> 4 -> 3 -> 2 -> 1。

请编写一个函数 reverseList,实现上述功能。

函数签名如下:

public ListNode reverseList(ListNode head) {
    // TODO: 实现函数体
}

其中,ListNode 是一个单链表节点的定义:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

提示:

  • 你可以迭代或递归地反转链表。
  • 你能否用 O(1) 的空间复杂度解决此问题?

祝你好运!

解题思路和答案

链表的反转是一个经典的问题,有两种常见的解法:迭代和递归。

迭代法的思路是:从头节点开始,依次将每个节点的 next 指针指向它的前一个节点,最后返回新链表的头节点。

递归法的思路是:先递归地反转子链表,然后将当前节点的 next 指针指向前一个节点,最后返回新链表的头节点。

具体实现见下面的答案和代码。

答案:

以下是迭代法的实现:

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

以下是递归法的实现:

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

这两种方法的时间复杂度都是 O(n),其中 n 是链表的长度。迭代法的空间复杂度是 O(1),递归法的空间复杂度是 O(n),因为递归需要使用系统栈空间。

这道题还有一个进阶问题:如何用 O(1) 的空间复杂度解决此问题?可以使用迭代法和递归法的变形解法,这里不再赘述。

完整的 Java 代码如下:

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 迭代法
        // ListNode prev = null;
        // ListNode curr = head;
        // while (curr != null) {
        //     ListNode next = curr.next;
        //     curr.next = prev;
        //     prev = curr;
        //     curr = next;
        // }
        // return prev;

        // 递归法
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

如果需要了解完整的思路和新奇的例子,可以去力扣增强自己的算法实力。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: java 反转链表 指针 算法
最后更新:2023年 5月 12日

墨风如雪

一个热爱生活,热爱分享的程序员

打赏 点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

墨风如雪

一个热爱生活,热爱分享的程序员

最新 热点 随机
最新 热点 随机
开源世界新王炸:阿里的Qwen3-Coder,不止是写代码,它想成为你的数字同事 办公室里的“变形金刚”:科大讯飞X5,AI也敢“拔网线”! 降维打击!Mistral Voxtral:开源语音的“终结者”已上线! AI“游侠”降临A股:16个“大脑”组团“炒股”,30秒“算命”市场! 视频魔法来了!AI能实时“变脸”直播,连游戏画面也能瞬间换装? 告别“听指令”,AI要“自己动手”了!ChatGPT Agent,AI界的“全能选手”已上线!
2000万次呼唤背后,蓝骑士有了“赛博外挂”智能触手可及:Google Gemma-3n 系列模型,让万物皆能“思考”AI圈大地震!120亿参数的FLUX编辑器开源,你的显卡准备好了吗?告别抓耳挠腮!Gemini CLI,让你和你的终端聊上了天一张3090就能跑!腾讯混元A13B,这是给AI圈的降维打击?华为亮出王牌:70亿参数“特种兵”与720亿“航母”级模型同时开源
设计模式:责任链设计模式 教你如何使用USDT开通ChatGPT Plus/GPT4:国内用户的详细教程 新时代的NoSQL数据库 Apache HBase超详细 优化Shadowsocks-libev服务器以获得更好的表现 Deno来了!下一代Web开发神器,是时候抛弃Node.js了吗? Java多线程的原子类
标签聚合
deepseek 教程 算法 设计模式 AI 大模型 java spring

COPYRIGHT © 2023 墨风如雪博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

免责声明 - 隐私政策