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

classNode {

  Node next;

  String name;

  publicNode(String name) {

    this.name = name;

  }

  /**

   * 打印结点

   */

  publicvoidshow() {

    Node temp =this;

    do{

      System.out.print(temp +"->");

      temp = temp.next;

    }while(temp !=null);

    System.out.println();

  }

  /**

   * 递归实现单链表反转,注意：单链表过长，会出现StackOverflowError

   * @param n

   * @return

   */

  publicstaticNode recursionReverse(Node n) {

    longstart = System.currentTimeMillis();

    if(n ==null|| n.next ==null) {

      returnn;

    }

    Node reverseNode = recursionReverse(n.next);

    n.next.next = n;

    n.next =null;

    System.out.println("递归逆置耗时:"+ (System.currentTimeMillis() - start) +"ms...");

    returnreverseNode;

  }

  /**

   * 循环实现单链表反转

   * @param n

   * @return

   */

  publicstaticNode loopReverse(Node n) {

    longstart = System.currentTimeMillis();

    if(n ==null|| n.next ==null) {

      returnn;

    }

    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...");

    returnpre;

  }

  @Override

  publicString toString() {

    returnname;

  }

  publicstaticvoidmain(String[] args) {

    intlen =10;

    Node[] nodes =newNode[len];

    for(inti =0; i < len; i++) {

      nodes[i] =newNode(i +"");

    }

    for(inti =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();

  } 

}