java 实现单链表逆转详解及实例代码
java实现单链表逆转详解
实例代码：
classNode{
Nodenext;
Stringname;
publicNode(Stringname){
this.name=name;
}
/**
*打印结点
*/
publicvoidshow(){
Nodetemp=this;
do{
System.out.print(temp+"->");
temp=temp.next;
}while(temp!=null);
System.out.println();
}
/**
*递归实现单链表反转,注意：单链表过长，会出现StackOverflowError
*@paramn
*@return
*/
publicstaticNoderecursionReverse(Noden){
longstart=System.currentTimeMillis();
if(n==null||n.next==null){
returnn;
}
NodereverseNode=recursionReverse(n.next);
n.next.next=n;
n.next=null;
System.out.println("递归逆置耗时:"+(System.currentTimeMillis()-start)+"ms...");
returnreverseNode;
}
/**
*循环实现单链表反转
*@paramn
*@return
*/
publicstaticNodeloopReverse(Noden){
longstart=System.currentTimeMillis();
if(n==null||n.next==null){
returnn;
}
Nodepre=n;
Nodecur=n.next;
Nodenext=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
publicStringtoString(){
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(InterruptedExceptione){
e.printStackTrace();
}*/
Noder1=Node.loopReverse(nodes[0]);
r1.show();
Noder=Node.recursionReverse(r1);
r.show();
}
}
总结
对于递归和循环，推荐使用循环实现，递归在单链表过大时，会出现StatckOverflowError,递归涉及到方法的调用，在性能上也弱于循环的实现
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！