题解 | #反转链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
    
       if (head != null && head.next != null) {
            ListNode ActualNext = head.next;
            ListNode lastNode = ReverseList(head.next);
            head.next = null;
            ActualNext.next =head;
            return lastNode;
        }
        return head;
    }
}

这道题做过无数八次了，但是再看还是会想半天，抓耳挠腮不堪其扰，现在我把思路记下来当做以后的提示总可以了吧！

反转链表：顾名思义就是把正向的指向变成翻过来如：1->2->3 变成 3->2->1,初看应该很简单直接循环把 node 节点保存在 list 中再反向遍历 list 把 node 一个一个的 next 到前一个后面。

这种办法可行但是太过于暴力，时间复杂度太高了。相同的数据进行循环，那能不能用递归来解决呢？

我们是要把下一个 node 变成前一个 node 的父节点，那我们就先在代码里面写下 head.next 获取到下一个节点吧！我们是要最后把 lastnode 节点给返回成父节点的，所以直接进行递归传入 head.next 返回的 node 就是我们的 lastnode 节点，好了往下走我们进行 head.next.next的赋值ActualNext.next =head;在把 head.next = null 断开和后一个节点的联系。这样 1 节点后面就不会是 2了。

完美！！！