java單鏈表逆序用法代碼示例

2024-07-13 10:17:21

字體：大中小

來源：轉載

供稿：網友

本篇博客，比較簡單。對單鏈表逆序不理解的看看就可以了。

逆序思想

現假設有一鏈表，有待逆序操作。我們首先想到的就是將那個指針關系逆序了就行了唄。

事實上，就是這樣。博主就是以這個為目標來完成的單鏈表逆序操作。

javascript/59172.html">java;">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了。

不斷逆序。

java,單鏈表,逆序,java單鏈表逆序解釋,單鏈表的逆序,單鏈表逆序輸出

抱歉，手抖了一下，畫錯了。大家見諒。手繪圖上的第五次示意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;	}}

測試結果：