重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

java中如何实现逆转单链表

java中如何实现逆转单链表?很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

创新互联建站是一家专业提供满城企业网站建设,专注与成都网站设计、做网站、H5页面制作、小程序制作等业务。10年已为满城众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。

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,递归涉及到方法的调用,在性能上也弱于循环的实现

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注创新互联行业资讯频道,感谢您对创新互联的支持。


当前标题:java中如何实现逆转单链表
地址分享:http://cqcxhl.com/article/ggcpos.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP