實例代碼：
|
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
