反转链表经典题

题目链接-来源：力扣（LeetCode）

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：

反转链表经典解法无非两种，一是递归法，二是用指针遍历链表迭代操作。
指针遍历较为直观，且占用常数空间。但递归法容易写出较为简洁的代码，这里介绍递归法。
首先，每次递归都假设当前节点的下下个节点及以后已经实现了反转，由于我们要获取反转后的链表头（也就是原链表的表尾），这个链表头就需要我们通过递归函数层层返回上来。我们用一个变量 newHead 记录之。
然后我们只需要关注当前节点与下个进行反转即可。先让下个节点的尾部指向自己，再将当前节点尾部置为 null，即完成了当前层的递归，最后记得将前面记录的 newHead 返回给上层函数。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        
        return reverseHelper(head);
    }
    
    private ListNode reverseHelper(ListNode head) {
        
        ListNode nextNode = head.next;
        if (nextNode == null) {
            return head;
        }
        
        ListNode newHead = reverseHelper(nextNode);
        nextNode.next = head;
        head.next = null;
        
        return newHead;        
    }
}