本篇博客,比較簡單。對單鍊錶逆序不理解的看看就可以了。
逆序思想
現假設有一鍊錶,有待逆序操作。我們首先想到的就是將那個指針關係逆序了就行了唄。
事實上,就是這樣。博主就是以這個為目標來完成的單鍊錶逆序操作。
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這行代碼執行完成後,我們原始的那個head節點的next將變成null,也就是我們整個鍊錶的null了。
想像一下,原來的那個鍊錶的最後面的next不也是一個null嗎?這里道理是一致的。
此時,更新pre為原來的head節點,也是為了下一步的逆序做準備,而head也自然的變成了原來的head.next了。
抱歉,手抖了一下,畫錯了。大家見諒。手繪圖上的第五次示意pre節點應該在節點5的位置,沒有了head。
從圖例中我們也不難看出,我們就是一次次的將head向後移,同時更新pre節點,來達到逆序的效果。
代碼
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;}}測試
經測試,代碼輸出正確。
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
幫助理解,下面是另一個實例:
/** * java 實現單鍊錶的逆序* @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單鍊錶逆序用法代碼示例的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題,如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!