剑指offer和leetcode都有的_反转链表

输入一个链表，反转链表后，输出链表的所有元素。

　　一开始我的做法非常复杂，因为我一次变了两个指针，导致要分别判断单数个结点和偶数个结点的情况。

　　反转链表要解决的两个问题就是

　　1.结点指向它的前驱

　　2.头结点变为其尾结点

　　

　　当反转一个结点时，假设反转i,首先需要记录它的前驱，让它指向它的前驱，还需要记录它的后继结点，否则就会造成链表的断裂，所以至少需要三个结点。

　　后来我整理了一下思路，发现有两种方法，一种用的是循环，一种用的是递归。

　　1.循环做法

/**循环做法来反转链表
 * 思路是用三个指针来记录，
 * newCur表示现在正在反转的指针
 * newNext表示newCur将要指向的指针
 * newPre表示下一个要进行反转的指针
 * 
 *
 */
public class ReverseLinkedListIterate {
	public static ListNode reverseLinkedList(ListNode head){
		 if(head==null||head.next==null){
			 return head;
		 }
		ListNode newPre=null;
		ListNode newCur=head;//指向头结点
		ListNode newNext=null;//指向头结点的前一个，也就是null
		while(newCur!=null) {
			newPre=newCur.next;
			newCur.next=newNext;
			newNext=newCur;
			newCur=newPre;
		}
		return newNext;
	}
}

　　2.递归做法

　　　　因为每个节点的操作其实是相同的，就是把节点指向前驱，所以我们想到了用递归的方法，但是在最后一步要做一些处理。

public static ListNode reverseLinkedList(ListNode head){
		 if(head==null||head.next==null){
			 return head;
		 }
		 return reverse(null,head);
	}
	/**
	 * 
	 * @param newNext 表示结点的前驱，该结点指向的新的结点
	 * @param newCurrent 表示当前结点
	 * @return
	 */
	public static ListNode reverse(ListNode newNext,ListNode newCurrent) {
		//当当前结点的下一个不为空时，即该结点不是最后一个结点时
		if(newCurrent.next!=null) {
			//先记录该结点的下一个结点
			ListNode newPrevious=newCurrent.next;
			//该结点指向前驱
			newCurrent.next=newNext;
			//再把下一个结点当做当前结点。
			return reverse(newCurrent,newPrevious);
			
		}
		//当当前结点为最后一个结点时，不需要再进行下一步了，但此时需要变换指针的指向
		newCurrent.next=newNext;
		//再把尾结点返回。
		return newCurrent;
	}