Java 详解如何从尾到头打印链表

目录
  • 1.题目
  • 2.解法
    • 2.1栈
    • 2.2递归
  • 3.复杂度
    • 3.1栈
    • 3.2递归

1.题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

题目来源：力扣（LeetCode）

2.解法

2.1栈

栈的特点是先进后出，所以我们创建一个栈，逐个将节点压入栈内，然后建立一个数组，将栈内的节点数值逐个弹出

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();//创建一个栈
        ListNode cur = head;
        //将节点压栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        int size = stack.size();//栈的长度
        int[] array = new int[size];//创建一个和栈一样长的数组
        //出栈入数组
        for (int i = 0; i < size; i++) {
            array[i] = stack.pop().val;
        }
        return array;
    }
}

2.2递归

public class PrintList {

    ArrayList<Integer> cur = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] array = new int[cur.size()];
        for (int i = 0; i <array.length; i++) {
            array[i] = cur.get(i);
        }
        return array;

    }

    public void recur(ListNode head) {
        if(head == null) {
            return ;
        }
        recur(head.next);
        cur.add(head.val);
    }

}

3.复杂度

3.1栈

时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

3.2递归

时间复杂度：O(n) 遍历链表，递归 NN次。

空间复杂度：O(n) 系统递归需要使用 O(N)的栈空间

到此这篇关于Java 详解如何从尾到头打印链表的文章就介绍到这了,更多相关Java 从尾到头打印链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java实现链表数据结构的方法

    Java实现链表数据结构的方法

    什么是链表? 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的.每一个链表都包含多个节点,节点又包含两个部分,一个是数据域(储存节点含有的信息),一个是引用域(储存下一个节点或者上一个节点的地址). 链表的理解示意图: 链表的特点是什么? 获取数据麻烦,需要遍历查找,比数组慢方便插入.删除 简单的链表的实现原理 创建一个节点类,其中节点类包含两个部分,第一个是数据域(你到时候要往节点里面储存的信息),第二个是引用域(相当于指针,单向链表有一个指

  • Java关于重排链表详细解析

    Java关于重排链表详细解析

    1.题目 给定一个单链表 L 的头节点 head ,单链表 L 表示为:  L0→ L1 → - → Ln-1 → Ln  请将其重新排列后变为: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → - 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换.  来源:力扣(LeetCode) 2.解析 将一个链表分为两个子链表,然后将其归并. 我们要先找到链表的中间节点,在中间节点将其断开 然后反转后半链表 再将两个子链表逐个连起来  将后半链表反转,独立成一个子链表. 最

  • Java实现单链表的操作

    Java实现单链表的操作

    本文实例为大家分享了Java实现单链表的基本操作,供大家参考,具体内容如下 顺序表:物理上逻辑上都连续:链表:物理上不一定连续,逻辑上一定连续的. 链表的概念及结构 概念:连表示一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是用过链表中的引用链接次序实现的. 8种链表结构: 单项.双向带头.不带头循环.非循环 主要的三种链表: 无头单项非循环链表.带头循环单链表.不带头双向循环链表 代码实现 1. 接口定义 package com.github.linked.Impl; publ

  • Java 详解分析链表的中间节点

    Java 详解分析链表的中间节点

    目录 1.题目描述 2.解法 3.复杂度 1.题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点. 如果有两个中间结点,则返回第二个中间结点. 题目来源:力扣(LeetCode) 2.解法 定义一个快指针 fast 和一个慢指针 slow :fast 走两步, slow 走一步,当 fas t走到尽头时, slow 就刚好在中间节点.因为 fast 比slow 多走一半路程 class Solution { public ListNode middleNode(ListNod

  • Java复杂链表的复制详解

    Java复杂链表的复制详解

    目录 1.题目 2.解法 2.1 拼接+拆分 3.代码 1.题目 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 2.解法 2.1 拼接+拆分 首先我们逐个将节点复制并且和原来的链表连起

  • java单链表使用总结

    链表的概念: 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列节点(链表中的每一个元素称为节点)组成,节点可以在运行时动态生成.每个节点包含两个部分:一个是存储数据元素的数据域,另一个是存储下一个节点地址的指针域.相对于线性表顺序结构,操作复杂.由于不必按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O

  • 带你了解Java数据结构和算法之链表

    带你了解Java数据结构和算法之链表

    目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结 前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会

  • Java实现无头双向链表操作

    Java实现无头双向链表操作

    本文实例为大家分享了Java实现无头双向链表的具体代码,供大家参考,具体内容如下 无头双向链表的结构: 代码分析 节点结构 class Node {     private int data;     private Node next;     private Node prev;     public Node(int data) {         this.data = data;         this.prev = null;         this.next = null;  

  • Java数据结构与算法学习之双向链表

    Java数据结构与算法学习之双向链表

    目录 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 2.双向链表的头结点 3.总代码 双向链表中的指定文件插入元素  1.插入的为第一个位置 2.其他位置插入 总代码 双向链表的删除 1.删除第一个元素 2.删除其他位置元素 总代码 双向链表的储存结构示意图 双向链表的初始化结构 1.双向链表的结点 代码实现 //双向链表的结点,包含一个数据域,两个指针域 typedef struct DoublyNode { ElementType date; //数据域 struct

  • Java 详解如何从尾到头打印链表

    Java 详解如何从尾到头打印链表

    目录 1.题目 2.解法 2.1栈 2.2递归 3.复杂度 3.1栈 3.2递归 1.题目 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回). 题目来源:力扣(LeetCode) 2.解法 2.1栈 栈的特点是先进后出,所以我们创建一个栈,逐个将节点压入栈内,然后建立一个数组,将栈内的节点数值逐个弹出 class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> stack = new

  • Java编程实现从尾到头打印链表代码实例

    问题描述:输入一个链表的头结点,从尾巴到头反过来打印出每个结点的值. 首先定义链表结点 public class ListNode { int val; ListNode next = null; ListNode(int val){ this.val = val; } } 思路1:此题明显想到是利用栈的思想,后进先出,先遍历链表,依次将结点值进栈.最后在遍历栈出栈. public static Stack<Integer> printListReverse_Stack(ListNode li

  • PHP从尾到头打印链表实例讲解

    题目 输入一个链表,从尾到头打印链表每个节点的值. 题解 一种是使用栈. 第二种是递归. 代码 //递归版本 function printListFromTailToHead($head) { if($head == NULL){ return []; } $arr = array(); $cur = $head; if($cur->next != null){ $arr = printListFromTailToHead($cur->next); } array_push($arr, $cu

  • 基于python实现从尾到头打印链表

    这篇文章主要介绍了基于python实现从尾到头打印链表,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目描述 输入一个链表,按链表从尾到头的顺序返回一个ArrayList. 思路 遍历链表,把结构保存在list里面,然后把list逆序输出 代码 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None

  • Java详解实现ATM机模拟系统

    Java详解实现ATM机模拟系统

    目录 一.概述 二.程序概要设计 三.程序详细设计 四.程序演示 一.概述 (1)选题分析 (2) 开发环境 开发环境,选择IDEA这一Java开发软件,基于JDK1.8版本,在本机window上开发本ATM模拟程序. 二.程序概要设计 (1) 功能模块设计 经过对题目的分析,把本ATM模拟程序分为管理员端和用户模式两大模块.其中,管理员具有查询所有账户.导出所有账户信息到文件.注销功能.用户模块具有查询余额.ATM转账.ATM存款.ATM取款.修改密码.查询交易记录.导出记录.退卡等功能. 系

  • java 详解类加载器的双亲委派及打破双亲委派

    java 详解类加载器的双亲委派及打破双亲委派 一般的场景中使用Java默认的类加载器即可,但有时为了达到某种目的又不得不实现自己的类加载器,例如为了达到类库的互相隔离,例如为了达到热部署重加载功能.这时就需要自己定义类加载器,每个类加载器加载各自的类库资源,以此达到资源隔离效果.在对资源的加载上可以沿用双亲委派机制,也可以打破双亲委派机制. 一.沿用双亲委派机制自定义类加载器很简单,只需继承ClassLoader类并重写findClass方法即可.如下例子: ①先定义一个待加载的类Test,它

  • Java 详解单向加密--MD5、SHA和HMAC及简单实现实例

    Java 详解单向加密--MD5、SHA和HMAC及简单实现实例

    Java 详解单向加密--MD5.SHA和HMAC及简单实现实例 概要: MD5.SHA.HMAC这三种加密算法,可谓是非可逆加密,就是不可解密的加密方法. MD5 MD5即Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致.MD5是输入不定长度信息,输出固定长度128-bits的算法. MD5算法具有以下特点: 1.压缩性:任意长度的数据,算出的MD5值长度都是固定的. 2.容易计算:从原数据计算出MD5值很容易. 3.抗修改性:对原数据进行任何

  • Java详解线上内存暴涨问题定位和解决方案

    Java详解线上内存暴涨问题定位和解决方案

    前因: 因为REST规范,定义资源获取接口使用GET请求,参数拼接在url上. 如果按上述定义,当参数过长,超过tomcat默认配置 max-http-header-size :8kb 会报一下错误信息: Request header is too large 可以修改springboot配置,调整请求头大小 server: max-http-header-size: xxx 后果: 如果max-http-header-size设置过大,会导致接口吞吐下降,jvm oom,内存泄漏. 因为tom

  • Java 详解异常的处理机制

    Java 详解异常的处理机制

    目录 1.异常概述与异常体系结构 1.1异常概述 1.2运行时异常与编译时异常 1.3异常体系结构 2.常见异常 1. ArrayIndexOutOfBoundsException 2.NullPointerException 3.ArithmeticException 4.ClassCastException 3.异常处理机制 3.1异常的抛出与捕获 3.2异常处理机制:try-catch-finally 5.用户自定义异常类 6.异常处理5个关键字 1.异常概述与异常体系结构 1.1异常概述

  • Java 详解循环屏障CyclicBarrier如何实现多线程分段等待执行完成

    Java 详解循环屏障CyclicBarrier如何实现多线程分段等待执行完成

    前言 工作中是否有这样的场景,多个线程任务,如果所有线程完成到某个阶段,你希望知道所有线程均完成该阶段.当然你使用线程计数可以实现,只是不够优雅. 所以我即:Java 多线程等待优雅的实现方式之Phaser同步屏障 之后再提供一个循环屏障,CyclicBarrier,更优雅的实现工具. Maven依赖 可以依赖,也可以不依赖,只是代码要稍微多一些,最好添加. <dependency> <groupId>org.projectlombok</groupId> <ar

随机推荐