题解 | #反转链表#

反转链表

http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

反转链表之前是这样的

反转之后是这样：

思路分析：

方法一：迭代

反转链表就是将每个节点的 -> 指向这个节点的前一个节点。咱先不想代码怎么写，就以上面的图为例，比如以 “2” 这个节点（为了更好理解，假设“1”节点已经反转完毕）为例，我想反转这个节点该咋做？是不是主要三步走：

找到 当前节点，也就是被反转的节点，这里假设是 “2” 这个节点。
我们不是要指向前一个节点嘛，那我需要确定找到 当前节点 的 前置节点，然后将当前节点的 next 指向前一个节点。
其实到这里当前节点的反转已经完毕了，但因为我们已经将当前节点的 next 指向前置节点了，所以和下一个节点就没有连接了，这会导致下一个节点在反转的时候找不到前置节点，所以我们要把当前节点的下一个节点（也就是后置节点）保存下来，以供后置节点来反转，并且会把“后置节点”继续当作“当前节点”来重复这个动作，直到结束。

AC代码

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode node = head;
        // 用于当作每个节点的前一个节点
        ListNode prev = null;

        while (node != null) {
            // 先存储每当前点的下一个节点 
            ListNode next = node.next;
            // 将当前节点的 next 指针指向前一个节点
            node.next = prev;
            // 将当前节点作为下一个节点的前置节点
            prev = node;
            // 将 后置节点 继续当作 当前节点来重复这个动作
            node = next;
        }
        return prev;
    }
}

时间复杂度：O(n),其中 n 是链表的长度，要遍历一次链表
空间复杂度:O(1)。

方法二：递归

反转链表除了用上面迭代的思维做，还可以用递归来实现，相信大多数小伙伴会觉得递归稍微复杂一些，不好理解，其实我刚做的时候也是这么觉得，可是当我理解了这题的精髓之后发现递归远远要比迭代好理解的多，哈哈哈，你们也不用不信，接下来咱们好好剖析一下就知道了。
再讲之前和大家聊聊啥是递归，其实在网上是可以找到很多关于递归的解释的，不过在我这里我认为，递归就是对同一个节点做相同的操作，以此来处理某种场景。
图片说明
文字解说：
（1）先递归，递归到倒数第二个节点，因为倒数第一个节点是最后一个节点，没有next节点。
（2）此时来到了倒数第二个节点“3”，此时的目的就是将节点“3”和节点“4”中间的 “->” 变为 “<-”，这个也好弄，只需要将节点“3” 的next节点“4”的next指针指向节点“3”本身就 OK 了，然后将节点“3”的next指针指向 null 即可，至此，节点“3”的反转就完成了，是不是炒鸡简单！
（3）然后到了节点“2”，只需要重复节点“3”的动作即可，节点“1”也是如此。这样整个链表的反转就完事了，没骗你们吧，确实很简单滴。

接下来上代码！！！

AC 代码

public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 已经到最后一个节点了，返回 作为新链表的头节点
        if (head == null || head.next == null) {
            return head;
        }
        // 得到新链表的头节点，这个头节点上 head.next，head 是倒数第二个节点
        ListNode newHead = ReverseList(head.next);
        // 将倒数第二个节点 head 的 next 节点的 next 指针指向 head本身
        head.next.next = head;
        // 将 head 的next 指针指向 null，至此 head 节点就反转完了
        head.next = null;
        // 返回头节点，继续处理之前的节点
        return newHead;
    }
}

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。