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,递归涉及到方法的调用,在性能上也弱于循环的实现
分享到:
相关推荐
主要介绍了java 实现单链表逆转实例代码的相关资料,需要的朋友可以参考下
使用C++描述的单链表处理程序源代码,可以实现单链表的逆转等操作。CodeBlocks下调试通过。
单链表逆转操作,在笔试中经常可见 1实现整体逆转 2.实现相邻元素逆转
经典单链表的创建与单链表项的逆转,C++代码实现
C++ 实验 包含3个文件reverse.cpp CirHSLinkedList.h Node.h
一个C程序 实现了单链表的逆序 且复杂度为O n
单链表的逆转求和,根据输入,完成单链表的建立操作,然后实现单链表的逆转,输出逆转之后各几点的元素值,最后输出所有元素之和。
编写一个程序,使程序实现在单链表的某给定节点后插入新节点的算法,如找不到则插在尾部;并且能够查找给定节点并且删除;以及编写单链表逆转的算法。
逆转线性单链表.doc逆转线性单链表.doc逆转线性单链表.doc逆转线性单链表.doc
3_单链表的逆转.cpp
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
template<class T> //定义在“LinkedChain.h” struct ChainNode //链表结点类的定义 { T data; //数据域 ChainNode<T> *link; //链指针域 ChainNode() //构造函数 { link=NULL;... ChainNode(T item,ChainNode...
详细描述了单链表逆转的思路及过程,并附源码
c++实现单链表的创建,逆转,以及找到寻找中间节点,用最小的空间找到倒数第m个节点
数据结构的常用代码,对单链表的逆置,常用的数据结构代码
java 用递归实现字符串反转 java 用递归实现字符串反转
包括单链表的输入,输出和逆转后的输出。编译通过。
纯C语言实现,将文件包下载到本地目录,直接make即可产生list文件,直接执行即可
编制程序实现字符串的逆转功能。要求具有友好的输入、输出界面。如输入This is a test 输出 tset a si sihT