資料結構和算法_數組/連結清單反轉

問題：如何在不新增數組或者連結清單的基礎上，将原數組、連結清單反轉

1.數組反轉：

<思路>通過兩個位移指針l和r，l指向數組的第一個元素，r指向最後一個元素，然後在同一個循環中引入temp變量交換l指針和r指針對應的資料，交換完成以後同時向中間移動一步（l++，r--）一直到相遇為止。這裡這個循環的條件是左指針小于右指針

<代碼>

package 數組和連結清單;

public class ReverseArray {
	
	public static void main(String[] args){
		ReverseArray demo = new ReverseArray();
		
		int[] mylist = {5,89,67,918,3,46,768,12};
		System.out.println("原數組：");
		demo.printOut(mylist);  //列印原數組
		demo.reverseList(mylist);
		System.out.println("\n反轉後的數組：");
		demo.printOut(mylist);  //列印反轉後的數組
	}
	
	//列印數組的函數
	private void printOut(int[] list){
		int len = list.length;
		for(int i = 0;i<len;i++){
			System.out.print(list[i]+"\t");
		}
	}
	
	//反轉函數
	public void reverseList(int[] list){
		int len = list.length;
		int l = 0;
		int r = len-1;  //右指針
		int temp = 0;    //交換左右指針的時候引入的臨時變量
				
		//注意這裡的判斷交換停止的條件，數組長度的奇偶也要考慮
		while(l < r){
			temp = list[r];
			list[r] = list[l];
			list[l] = temp;
			l++;
			r--;
		}
	}
	
}
           

連結清單反轉

<思路>采用遞歸算法，為甚麼想到用遞歸算法，因為給你一個連結清單的頭部，要我們反轉，就必須從連結清單的最後一個開始操作，也就是說要先從頭節點向下找到尾節點，然後再從尾節點逐層操作傳回到頭結點，這種自頂向下，從大到小，然後從小或者下反彈向上操作的過程就是遞歸的過程，是以采用遞歸的方法。算法裡面我們要做哪些事？1.遞歸的底部在哪裡，反彈條件是什麼。2.在遞歸到底部的時候，需要傳回麼，要傳回的話傳回什麼。3. 遞歸反彈以後的操作是什麼。這裡主要操作就是建立相鄰的兩個節點之間的新關系，讓後一個節點指向前一個，前一個節點指向null。

<代碼>

package 數組和連結清單;

import java.util.Random;

//節點定義
public class ReverseLink {
	class Node{
		Node next = null;
		int number =0;
	}
	
	//連結清單的節點裡面的值采用随機數産生
	private Random random = new Random(System.currentTimeMillis());
	
	public static void main(String[] args){
		ReverseLink demo = new ReverseLink();
		
		//建立連結清單
		Node head = demo.createLink(6);		
		//列印建立完的連結清單
		System.out.println("原始連結清單是：");
		demo.printLink(head);
		
		//反轉連結清單
		Node nHead = demo.reverseLink_recursive(head);
		//列印反轉後的連結清單
		System.out.println("\n反轉後的連結清單：");
		demo.printLink(nHead);
	}
	
	//遞歸法，反轉連結清單，傳回新的連結清單頭
	private Node reverseLink_recursive(Node head){   	//函數需要傳回頭節點
		if(head == null || head.next == null) //反彈條件是目前節點為空（防止一開始就傳入空連結清單）或者目前節點的next指向null（最後一個節點）
			return head;  //傳回原來連結清單的尾節點作為新連結清單的頭節點
		else{
			/**
			 * 這個部分是遞歸的核心，遞歸算法的核心是兩個問題：
			 * 1.分下去的時候，是在重複哪個過程(操作)？這裡是不斷讓目前節點産生下一次遞歸所需要的參數——子連結清單的頭節點
			 * 2.合上來的時候，需要在誰之間重建立立怎樣的關系？這裡的是在相鄰的兩個節點之間，讓後者的next指針指向前者，前者的next指針指向null
			 */
			//分的過程
			Node second_node = head.next; 
			Node nHead = reverseLink_recursive(second_node);
			
			//合的過程
			second_node.next = head;
			head.next = null;
			return nHead;
		}
	}
	
	
	//建立連結清單,傳回連結清單頭
	private Node createLink(int len){
		/**
		 * 1.建立連結清單關鍵是使用了head頭節點指針和tail尾節點指針
		 * 2.新增節點的過程就是不斷讓原連結清單tail節點的next指向新節點，然後tail指針指向新節點的過程
		 * 3.這樣建立的連結清單的head其實不是真的head，這個head的weight往往用來表示連結清單的長度
		 */
		Node head = new Node();
		Node tail = head;
		head.number = len;
		for(int i =0;i<len;i++){
			Node node = new Node();
			node.number = random.nextInt(100);
			tail.next = node;
			tail = node;
		}		
		return head;
	}

	//輸出列印連結清單
	private void printLink(Node head){
		Node temp = head;		
		while(temp != null){
			System.out.print(temp.number+"\t");
			temp = temp.next;
		}
		return;
	}
	
}