## 单链表的反转
一般单链表反转有三种方法
1. 链表转为数组反转后再转为链表
2. 递归反转
3. 三指针反转
### 链表和节点代码
```java
public class SinglyLinkedList {
/**
* head指针
*/
private Node head = null;
public SinglyLinkedList(){
head = new Node();
}
}
```
Node代码
```java
public Node next;
public int value;
Node(){}
Node(int value){
this.value = value;
}
```
### 数组转换法
这种方法就比较简单粗暴了,直接声明一个链表相同大小的数组,遍历链表,从数组的最后一位开始赋值,然后再遍历数组,将链表重新赋值,耗时O(n),空间大小O(n),所以这种方式一般不会使用
```java
/**
* @Description: 使用数组方法进行单链表的反转,浪费空间
* @Params: []
* @return: void
* @Author: zhengyao
* @Date: 2019/8/9
*/
private void reverseListByArray(){
if(reverseListLengthValidate()){
int[] array = new int[getLength()];
Node current = head.next;
int index = getLength() - 1;
//遍历链表,赋值给数组
while (current != null){
array[index] = current.value;
current = current.next;
index--;
}
//遍历数组,赋值给链表
Node reverseHead = head;
for (int value : array) {
reverseHead.next = new Node(value);
reverseHead = reverseHead.next;
}
}
}
```
### 递归法
其实就是递归到链表的最后一个节点,然后将每一个节点的next.next变成自己,就达到了反转链表的功能
```java
/**
* @Description: 反转链表,使用递归法进行反转,例如3->4->5->6,
* 递归之后就变成,当head等于5的时候,5->6->5->null,return 6,回来,就直接反转了整个节点
* @Params: []
* @return: void
* @Author: zhengyao
* @Date: 2019/8/9
*/
private void reverseList(){
Node curr = reverseListByre(head.next);
head.next = curr;
}
private Node reverseListByre(Node head){
if(head == null || head.next == null){
return head;
}
Node curr = reverseListByre(head.next);
//将本节点的next.next变成自己,就变成了反转了,我的下一步变成了我,然后将我的next置为null,否则会死循环
head.next.next = head;
head.next = null;
return curr;
}
```
### 三指针反转法
```java
/**
* @Description: 使用三个指针来反转链表
* @Params: []
* @return: void
* @Author: zhengyao
* @Date: 2019/8/9
*/
private void reverseListByPointer(){
if(reverseListLengthValidate()){
//head 不拿出来进行计算
Node curr = head.next;
Node prev = null;
while (curr != null){
// 先记录下当前指针的下一个,留着后面给curr指针移动使用
Node temp = curr.next;
// 最早的prev是null,后面每一次prev = 当前指针,留待下一个循环,指向前一个prev
curr.next = prev;
// 这里就是将prev = 当前指针,每次都比当前指针慢一步,相当于把原有的前置指针变为现有的后置指针
prev = curr;
// 当前指针移动到下一步
curr = temp;
}
head.next = prev;
}
}
```
单链表的反转