当前位置: 首页 > news >正文

坚持刷题|反转链表

文章目录

  • 题目
  • 思考
  • 实现
    • 1. 迭代方式实现链表翻转
    • 2. 递归方式实现链表翻转

Hello,大家好,我是阿月。坚持刷题,老年痴呆追不上我,今天继续链表:反转链表

题目

LCR 024. 反转链表
在这里插入图片描述

思考

翻转链表是一个常见的算法问题,通常用于练习基本的数据结构操作

实现

在 Java 中可以通过迭代和递归两种方式来实现链表的翻转

1. 迭代方式实现链表翻转

  • 使用三个指针prevcurrnextTemp来逐步翻转链表。
    • prev初始化为null,表示新链表的末尾。
    • curr从头节点开始,逐步遍历整个链表。
    • 在遍历过程中,将当前节点的next指向前一个节点,并移动prevcurr到下一个节点。
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public static ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next; // 保存下一个节点curr.next = prev; // 当前节点的next指向前一个节点prev = curr; // 前一个节点移动到当前节点curr = nextTemp; // 当前节点移动到下一个节点}return prev; // 返回新的头节点}public static void main(String[] args) {// 构建测试链表:1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 翻转链表ListNode reversedHead = reverseList(head);// 打印翻转后的链表ListNode current = reversedHead;while (current != null) {System.out.print(current.val + " ");current = current.next;}}
}

2. 递归方式实现链表翻转

  • 递归地处理链表的剩余部分,直到到达最后一个节点。
  • 在回溯过程中,翻转当前节点和其前一个节点的连接。
  • 最终返回新的头节点。
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class ReverseLinkedList {public static 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; // 返回新的头节点}public static void main(String[] args) {// 构建测试链表:1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);// 翻转链表ListNode reversedHead = reverseList(head);// 打印翻转后的链表ListNode current = reversedHead;while (current != null) {System.out.print(current.val + " ");current = current.next;}}
}

这两种方法在不同的场景下都有其优点和适用性。迭代方法通常更容易理解和实现,而递归方法则更具递归思想的优美性。

http://www.lryc.cn/news/376876.html

相关文章:

  • 升级和维护老旧LabVIEW程序
  • sqlite数据库整体迁移进mysql整个流程并解决中文异常问题
  • Hadoop3:MapReduce中的Partition原理及自定义Partition
  • 就因为没在大屏项目加全屏按钮,早上在地铁挨了领导一顿骂
  • STM32学习记录(八)————定时器输出PWM及舵机的控制
  • Vue CLI,Vue Router,Vuex
  • 互联网广告相关概念
  • 如何在服务器上部署一个java程序
  • 白酒:中国的酒文化的传承与发扬
  • 算法金 | 再见!!!梯度下降(多图)
  • python Django安装及怎么检测是否安装成功
  • Swift开发——存储属性与计算属性
  • 如何解决input输入时存在浏览器缓存问题?
  • Java基础学习-方法
  • Ribbon与Nginx的区别
  • R包开发详细教程
  • 图像的高频和低频细节
  • PostgreSQL源码分析——常量表达式化简
  • 速卖通自养号测评:安全高效的推广手段
  • 项目监督与控制
  • 【LeetCode刷题】面试题 17.19. 消失的两个数字
  • 如何定制Spring的错误json信息
  • 【第20章】Vue实战篇之Vue Router(路由)
  • 阿里云运维第一步(监控):开箱即用的监控
  • Python量化交易学习——Part7:定制增强型中证红利策略
  • 拥抱未来:探索改变游戏规则的新存储技术
  • shell中的流程控制
  • DiffIR: Efficient Diffusion Model for Image Restoration
  • xss一些笔记
  • 以太坊网络中为什么要设置Gas上限