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

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(http://);

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。