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

更新時間：2018年01月26日 15:54:07 作者：Marksinoberg

這篇文章主要介紹了java單鏈表逆序用法代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下

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

逆序思想

現(xiàn)假設(shè)有一鏈表，有待逆序操作。我們首先想到的就是將那個指針關(guān)系逆序了就行了唄。

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

Node pre = null;
Node post = null;

while(head!=null){
 post = head.next;
 head.next = pre;
 pre = head;
 head = post;
}

這便是逆序的核心了。下面我們就來一步步的講解。

首次逆序：

一開始的話，pre，post都設(shè)置為null。這是必須的，因為在head.next=pre這行代碼執(zhí)行完成后，我們原始的那個head節(jié)點的next將變成null，也就是我們整個鏈表的null了。

想象一下，原來的那個鏈表的最后面的next不也是一個null嗎？這里道理是一致的。

此時，更新pre為原來的head節(jié)點，也是為了下一步的逆序做準備，而head也自然的變成了原來的head.next了。

不斷逆序。

抱歉，手抖了一下，畫錯了。大家見諒。手繪圖上的第五次示意pre節(jié)點應(yīng)該在節(jié)點5的位置，沒有了head。

從圖例中我們也不難看出，我們就是一次次的將head向后移，同時更新pre節(jié)點，來達到逆序的效果。

代碼

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

幫助理解，下面是另一個實例：

/** 
 * 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;
	}
}

測試結(jié)果：