逆序思想
現(xiàn)假設有一鏈表，有待逆序操作。我們首先想到的就是將那個指針關系逆序了就行了唄。
事實上，就是這樣。博主就是以這個為目標來完成的單鏈表逆序操作。
java" id="highlighter_702464">
|
1
2
3
4
5
6
7
8
9
|
Node pre = null;Node post = null;while(head!=null){ post = head.next; head.next = pre; pre = head; head = post;} |
這便是逆序的核心了。下面我們就來一步步的講解。
- 首次逆序：
一開始的話，pre，post都設置為null。這是必須的，因為在head.next=pre這行代碼執(zhí)行完成后，我們原始的那個head節(jié)點的next將變成null，也就是我們整個鏈表的null了。
想象一下，原來的那個鏈表的最后面的next不也是一個null嗎？這里道理是一致的。
此時，更新pre為原來的head節(jié)點，也是為了下一步的逆序做準備，而head也自然的變成了原來的head.next了。
- 不斷逆序。
抱歉，手抖了一下，畫錯了。大家見諒。手繪圖上的第五次示意pre節(jié)點應該在節(jié)點5的位置，沒有了head。
從圖例中我們也不難看出，我們就是一次次的將head向后移，同時更新pre節(jié)點，來達到逆序的效果。
代碼
|
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
|
package list;public class ReverseList { public static void main(String[] args) { Node head = new Node(1); int[] value = {2,3,4,5}; Node temp = head; for (int i = 0 ; i< value.length;i++) { Node node = new Node(value[i]); temp.next = node; temp = temp.next; } printList(head); // 反序輸出一個單鏈表 head = reverse(head); printList(head); // 再次反向 head = reverseSingleList(head); printList(head); } public static void printList(Node head) { while(head!=null) { System.out.print("\t"+head.value); head = head.next; } System.out.println(); } public static Node reverse(Node head) { Node pre = null; Node post = null; while(head!=null) { post = head.next; head.next = pre; pre = head; head = post; } return pre; } public static Node reverseSingleList(Node head) { Node pre = null; Node next = null; while(head!=null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }}class Node { public int value; public Node next; public Node(int value) { this.value = value; }} |
測試
經(jīng)測試，代碼輸出正確。
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
幫助理解，下面是另一個實例：
|
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
|
/** * java 實現(xiàn)單鏈表的逆序 * @author Administrator * */public class SingleLinkedReverse { class Node{ int data; Node next; public Node(int data){ this.data = data; } } public static void main(String[] args) { SingleLinkedReverse slr = new SingleLinkedReverse(); Node head, tail; head = tail = slr.new Node(0); for (int i=1; i<10; i++){ Node p = slr.new Node(i); tail.next = p; tail = p; } tail = head; while(tail != null){ System.out.print(tail.data+" "); tail = tail.next; } head = reverse(head); System.out.println(" "); while(head != null){ System.out.print(head.data+" "); head = head.next; } } private static Node reverse(Node head) { Node p1,p2 = null; p1 = head; while(head.next != null){ p2 = head.next; head.next = p2.next; p2.next = p1; p1 = p2; } return p2; }} |
測試結果：
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
總結
以上就是本文關于java單鏈表逆序用法代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/marksinoberg/article/details/52490318
