题解 | #反转链表#

第一次用递归写的，自己很笨，所以这道题花了一个半小时，我递归学了很久一直很懵懂，我真的学哭了，但是幸好自己坚持下来了，我记忆力很差，反应也很慢，有的东西老师讲了很多遍我还是听不懂，心态也是那种玻璃心，所以大家都叫我林黛玉（==虽然我是男的），我希望成为一名合格的Java开发工程师，虽然职业生涯很短，但是人就活这几十年，好好的做自己喜欢的事吧。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
  
    // 定义头节点
    private static ListNode root = new ListNode(-1);

    public static ListNode ReverseList(ListNode head) {
        // 用一个变量保存了root的头节点地址(其实可以不用，直接返回root.next也可以)
        ListNode res = root;
        
        // 如果当前的链表为空或者只有一个头节点那么就不需要操作，直接返回即可
        if (head == null || head.next == null) {
            return head;
        }
        
        // 辅助方法
        dfs(head, root);

        // 因为设置了虚拟头节点，所以从next开始
        return res.next;
    }
    
     // 时间复杂度：o(len(ListNode)), 性能还是很低的，希望有师兄可以多提提意见
     private static ListNode dfs(ListNode head, ListNode root) {
        // 递归出口
        if (head.next == null) {
            root.next = head;
            return head;
        }

        // 递归体
        ListNode tmp = dfs(head.next, root); 
       
        // 递归结束需要进行的操作
        head.next = null; // 将节点独立出来，防止无限循环 3 - 2 - 3 - 2....
        tmp.next = head;  // 反转链表
       
        // 返回节点(比如3 -2 我们应该要把2这个节点返回)
        return head;
    }

}