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,递归涉及到方法的调用，在性能上也弱于循环的实现
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
idea ssm项目java程序向串口发送指令并且使用十六进制 rxtx包的方法
网友评论