数据结构和算法_数组/链表反转

问题：如何在不新增数组或者链表的基础上，将原数组、链表反转

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