[数据结构与算法]【数据结构】反转链表的实现思路（java版详细代码）

基本思路

• ！！注意链表结构！！想要找到一个元素，只能找到该元素的上一个元素.next获得

反转链表的方法

• 【头插法】：造新链表，把原链表依次 头插到新的链表
• 【递归法】：定义递归方法，明确递归的定义，直接递归，再次强调！！！不要钻到递归里面一个一个尝试！！！
• 【空间法】：直接放到别的数据结构中，如栈、数组

【头插法】

//ListNode 是定义的单链表结构
//head 是传进来单链表的头部
//假如是 1->2->3->4
public  ListNode  reverse(ListNode head){
	//base-case处理，如果链表是空、或者只有一个元素，直接返回
	if(head==null ||head.next==null) return head;

	//定义新的链表和临时变量
	ListNode newList=null;//新链表的头指针是空的

	ListNode tmp=head;
	
	//循环处理
	while(tmp!=null){
		ListNode nextList=tmp.next;  //先把剩下的链表保存
		
		tmp.next=newList; // 把tmp依次倒置  1  2->1  3->2->1  4->3->2->1
		newList=tmp; // 把tmp赋值给newList  
		
		tmp=nextList; //tmp回到原链表，再往下走
	}
	return newList;

}

【递归法】

//ListNode 是定义的单链表结构
//head 是传进来单链表的头部
//递归的定义：将链表倒置！！
//假如是 1->2->3->4
public  ListNode  reverse(ListNode head){
	//base-case处理，如果链表是空、或者只有一个元素，直接返回
	if(head==null ||head.next==null) return head;

	//将链表递归反转
	ListNode newList=reverse(head.next);//倒置了这一部分 null<-2<-3<-4
										//		
	//单独处理头部
	head.next.next=head;//把1->2->null  变成1<-2
	head.next=null;//把头变成尾。 1->null
	
	return newList;

}