单链表 和 双链表的翻转
链表的属于非常基础的数据结构，但是想要完成好它需要大量的练习，才能够在面试中不慌不乱的写好。
先分享今天听到的一个理论，来自《考试脑科学这本书》中：书中阐述了关于如何将普通的记忆转换成长期记忆。长期记忆的管理员是一个叫海马体的东西，由这个管理员来判断这个记忆是否值得放进长期记忆存储区域。那这个管理员判断的标准是什么呢？
标准是这个东西跟生活的危险有没有关系，你只要被开水壶烫过一次你就会永远记住不能摸开水壶。那么跟生活危险没关系的知识想要进入长期存储区怎么办？那只能去欺骗海马体了。。想要欺骗它你需要的重复练习，一直在管理员面前转悠，这时候管理员就会在想，这人是不是真的有事 啊？要不要放它进去？进去了长期记忆就形成了。
还有一个方法，将自己置于对自己稍微不利的境地（当然这里指的是不太严重的！！），比如说肚子饿的时候，这时候海马体就会把你和危险联系起来，这时候就是背东西的最好时机了！冲冲冲
接下来开始看单链表翻转的练习
首先我们来看看单链表的翻转的代码，然后会画图来解释这个代码是怎么回事：
最简单的链表翻转当然是用java中的容器去做，将链表左右节点都放入容器中，然后反向遍历容器中的元素连接就行了，这样额外空间复杂度是的，这里就不做代码阐述了。这里主要讲的是如何用额外空间复杂度
去翻转链表。
public class ReverseList {
public static class Node { // 基本的链表节点声明
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
public static Node reverseLinkedList(Node head){
Node pre = null; // 记录 头节点的 前一个地方 的指针
Node next = null; // 记录 头节点的 下一个要去的地方 的指针
while(head != null){
next = head.next; // 首先 先要记录好头节点的下一个地方，才不至于翻转之后不知道下一个地方要去哪
head.next = pre; // 然后将 头节点的下一个地方 指向头节点的前一个地方
pre = head; // 将 记录头节点的前一个地方的指针 移动到头指针的地方
head = next; // 然后头指针也移动到下一个地方，循环往复直到头指针指向空处
}
return pre; // 记住我们要返回的是头指针前一个节点哦！因为头指针最终会指向空
}
}
①：循环之前我们先准备好两个指针，一个是pre一个是next，pre指向的是head前面的一个节点！！
②：然后开始进入循环，循环的条件是head指向空就终止！！这时候我们先记录head的下一个环境，当head的指针往前指的时候我们就还能找到它下一个节点在哪。
③：这时候将head.next指向他的前一个环境，也就是pre。因为pre是空所以next就置为空了。
④：接下来我们需要做的就是将pre和head向前移动，所以第四歩就是将pre移动到head的位置。
⑤：将head移动到next的地方。
当head指向C的时候循环是不会判断为空的，所以这时候它还会进一次循环，然后指向空，所以最后一个循环的时候pre会指向C，所以我们最终会返回pre当成头节点。
注：图中有些地方画的不准确，为了方便理解。
接下来是双向链表，代码和单链表一样，只多了一行，用来维护last的代码：
public class ReverseDoubleLinkedList {
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
public static DoubleNode reverseDoubleList(DoubleNode head){
DoubleNode pre = null;
DoubleNode next = null;
while(head != null){
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
}
Reference： https://italk.mashibing.com/course/detail/cour_00004003
