算法分享系列No.1---- 反转链表

一、该题基础信息列表

1. 题目难易分类【easy--】【middle】【hard—】
2. 题目频率(牛客有考察次数)【高频】(10<=考察次数) 【中频】(2 <=考察次数 < 10) 【普通】

二、【反转链表】编程练习目标：

务必要熟练手写，目前大厂面试分两种模式：

模式一：只要求写出核心代码实现

模式二：手撕全部流程（结构体+核心代码实现+测试用例），完整流程

作为大厂面试官，我会选择模式二，因为模式二是考察一个人对基础知识扎实程度的，我自身就是这样，这道常规题【反转链表】的核心代码实现不会卡，但是如果完整写出结构体和所有测试用例及输出，未必能一次编译通过。

因此针对这道题的目标（反转链表经典题）：

1、能够熟练手撕完整流程，包含 1-1结构体，1-2核心代码实现， 1-3 所有测试用例（包括特殊用例，null , 边界问题等）

2、能够掌握两种解题方法，非递归 & 递归

三、刷题步骤

3-1、题目 反转链表

3-2、深度理解：单链表的【引申】相关内容

（1）链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用【递归】来处理。

（2）不同于数组，链表不能直接获取任意节点的值，必须通过指针找到该节点后才能获取其值

（3）链表长度无法直接获取，在未遍历到链表结尾时，无法知道链表的长度。

（4）进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。因此对应解决方案有两个：

（4-1）是尽量处理当前节点的下一个节点而非当前节点本身，

（4-2）是建立一个虚拟节点 (dummy node)，使其指向当前链表的头节点，这样即使原链表所有节点全被删除，也会有一个 dummy 存在，返回 dummy->next 即可

3-3、手撕代码全过程【JAVA版】含图解

（1）结构体

必要结构体：最基本赋值

class ListNode{
   int val;
   ListNode next;
   ListNode(int val){
       this.val = val;
   }
}

完整结构体

class ListNode{
   int val;
   ListNode next;
   ListNode(){}
   ListNode(int val){
      this.val = val;
   }
   ListNode(int val, ListNode next){
      this.val = val;
      this.next = next;
   }
}

(2) 实现函数【这道题要掌握 递归 & 非递归】两种代码实现解法

(2-1) 图解思路图下：

(2-2) 【非递归】代码实现：目前【非递归】解法求解<反转链表>这道题最为常见

//非递归思路
public class Solution{
   public ListNode ReverseList(ListNode head){
       ListNode pre = null;
       while(head != null){
           ListNode next = head.next;
           head.next = pre;
           pre = head;
           head = next;
       }
   }
   return pre;
}

（2-3）【递归】代码实现

//递归代码实现
public class Solution{
   public class ReverseList(ListNode head){
       return innerReverse(head, null);
   }

   private ListNode innerReverse(ListNode head, ListNode pre){
       //递归结束，这个时候返回整个链表的头指针
       if(head == null)
           return pre;
       ListNode next = head.next;
       head.next = pre;
       return innerReverse(next, head);
   }
}

（3）自测用例

为了显示方便，使用print函数进行打印

用例1: {1,2,3,4,5}

用例2: {}