欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-06 13:28:37
java 实现单链表逆转详解 实例代码: class node { node next; string name; public nod...

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(); 
  } 
 
  /** 
   * 递归实现单链表反转,注意:单链表过长,会出现*error 
   * @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,递归涉及到方法的调用,在性能上也弱于循环的实现

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