java 实现单链表逆转详解及实例代码

java 实现单链表逆转详解

实例代码：

class Node {
  Node next;
  String name;
  public Node(String name) {
    this.name = name;
  } 

  /**
   * 打印结点
   */
  public void show() {
    Node temp = this;
    do {
      System.out.print(temp + "->");
      temp = temp.next;
    }while(temp != null);
    System.out.println();
  } 

  /**
   * 递归实现单链表反转,注意：单链表过长，会出现StackOverflowError
   * @param n
   * @return
   */
  public static Node recursionReverse(Node n) {
    long start = System.currentTimeMillis();
    if(n == null || n.next == null) {
      return n;
    }
    Node reverseNode = recursionReverse(n.next); 

    n.next.next = n;
    n.next = null;
    System.out.println("递归逆置耗时:" + (System.currentTimeMillis() - start) + "ms...");
    return reverseNode;
  } 

  /**
   * 循环实现单链表反转
   * @param n
   * @return
   */
  public static Node loopReverse(Node n) {
    long start = System.currentTimeMillis();
    if(n == null || n.next == null) {
      return n;
    } 

    Node pre = n;
    Node cur = n.next;
    Node next = null;
    while(cur != null) {
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    n.next = null;
    n = pre;
    System.out.println("循环逆置耗时:" + (System.currentTimeMillis() - start) + "ms...");
    return pre;
  } 

  @Override
  public String toString() {
    return name;
  }
　　
　　public static void main(String[] args) { 

    int len = 10;
    Node[] nodes = new Node[len];
    for(int i = 0; i < len; i++) {
      nodes[i] = new Node(i + "");
    }
    for(int i = 0; i < len - 1; i++) {
      nodes[i].next = nodes[i+1];
    }
    /* try {
      Thread.sleep(120000);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }*/
    Node r1 = Node.loopReverse(nodes[0]);
    r1.show();
    Node r = Node.recursionReverse(r1);
    r.show(); 

  }　
}

总结

对于递归和循环，推荐使用循环实现，递归在单链表过大时，会出现StatckOverflowError,递归涉及到方法的调用，在性能上也弱于循环的实现

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • java 中链表的定义与使用方法

    java 中链表的定义与使用方法 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; 实例代码: package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new my

  • Java面试题-实现复杂链表的复制代码分享

    阿里终面在线编程题,写出来与大家分享一下 有一个单向链表,每个节点都包含一个random指针,指向本链表中的某个节点或者为空,写一个深度拷贝函数,拷贝整个链表,包括random指针.尽可能考虑可能的异常情况. 算法如下: /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.labe

  • Java实现单链表翻转实例代码

    Java实现单链表翻转实例代码

    Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

  • java 实现单链表逆转详解及实例代码

    java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o

  • java LRU(Least Recently Used )详解及实例代码

    java LRU(Least Recently Used )详解 LRU是Least Recently Used 的缩写,翻译过来就是"最近最少使用",LRU缓存就是使用这种原理实现,简单的说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉,比如我们缓存10000条数据,当数据小于10000时可以随意添加,当超过10000时就需要把新的数据添加进来,同时要把过期数据删除,以确保我们最大缓存10000条,那怎么确定删除哪条过期数据呢,采用LRU算法实现的话就是将最老的数据

  • Java 装箱与拆箱详解及实例代码

    Java 装箱与拆箱详解 前言: 要理解装箱和拆箱的概念,就要理解Java数据类型 装箱:把基本类型用它们相应的引用类型包装起来,使其具有对象的性质.int包装成Integer.float包装成Float 拆箱:和装箱相反,将引用类型的对象简化成值类型的数据 Integer a = 100; 这是自动装箱 (编译器调用的是static Integer valueOf(int i)) int b = new Integer(100); 这是自动拆箱 看下面一段代码 m1 public class

  • Java 使用json-lib处理JSON详解及实例代码

    Java 使用json-lib处理JSON详解 [项目环境] <dependency> <groupId>net.sf.json-lib</groupId> <artifactId>json-lib</artifactId> <version>2.4</version> <classifier>jdk15</classifier> </dependency> 1. JSON 数组对象转化

  • Java中的Static class详解及实例代码

     Java中的Static class详解 Java中的类可以是static吗?答案是可以.在Java中我们可以有静态实例变量.静态方法.静态块.类也可以是静态的. java允许我们在一个类里面定义静态类.比如内部类(nested class).把nested class封闭起来的类叫外部类.在java中,我们不能用static修饰顶级类(top level class).只有内部类可以为static. 静态内部类和非静态内部类之间到底有什么不同呢?下面是两者间主要的不同. (1)内部静态类不需

  • C++/java 继承类的多态详解及实例代码

    C++/java 继承类的多态详解 学过C++和Java的人都知道,他们二者由于都可以进行面向对象编程,而面向对象编程的三大特性就是封装.继承.多态,所有今天我们就来简单了解一下C++和Java在多态这方面的不同. 首先我们各看一个案例. C++ //测试继承与多态 class Animal { public: char name[128]; char behavior[128]; void outPut() { cout << "Animal" << endl

  • Java大文件上传详解及实例代码

    Java大文件上传详解 前言: 上周遇到这样一个问题,客户上传高清视频(1G以上)的时候上传失败. 一开始以为是session过期或者文件大小受系统限制,导致的错误.查看了系统的配置文件没有看到文件大小限制,web.xml中seesiontimeout是30,我把它改成了120.但还是不行,有时候10分钟就崩了. 同事说,可能是客户这里服务器网络波动导致网络连接断开,我觉得有点道理.但是我在本地测试的时候发觉上传也失败,网络原因排除. 看了日志,错误为: java.lang.OutOfMemor

  • java实现单链表增删改查的实例代码详解

    package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l

  • Java中的代理模式详解及实例代码

    java 代理模式详解 前言: 在某些情况下,一个客户不想或者不能直接引用一个对象,此时可以通过一个称之为"代理"的第三者来实现间接引用.代理对象可以在客户端和目标对象之间起到 中介的作用,并且可以通过代理对象去掉客户不能看到 的内容和服务或者添加客户需要的额外服务. 简单来说代理模式就是通过一个代理对象去访问一个实际对象,并且可以像装饰模式一样给对象添加一些功能. 静态代理 所谓静态代理即在程序运行前代理类就已经存在,也就是说我们编写代码的时候就已经把代理类的代码写好了,而动态代理则

  • java 反射和动态代理详解及实例代码

    一.java中的反射 1.通过反射加载类的属性和方法实例代码: /** * java.lang.Class 是反射的源头 * 我们创建了一个类,通过编译(javac.exe)生成对应的class文件,之后我们通过java.exe加载(jvm的类加载器加载)此class文件 * 此class文件加载到内存后,就是一个运行时类,存在缓存区,这个运行时类本事就是一个Class的实例 * 每一个运行时类只加载一次, */ Class<StudentExam> clazz = StudentExam.c

随机推荐