## 单链表的反转 一般单链表反转有三种方法 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; } } ```