实例代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
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,递归涉及到方法的调用,在性能上也弱于循环的实现
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
原文链接:http://asflex.iteye.com/blog/2084962