链表反转是将一个单链表倒转过来，即从1 -> 2 -> 3转换至3 -> 2 -> 1，题目如下

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

示例:

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

迭代

首先可以通过迭代链表，依次将当前节点的下一个节点指向当前节点的下一个节点

变量curr代表当前节点，在开始迭代前，curr应指向头结点，通过上一步分析，每次节点的变化规则为

ListNode curr = head;
curr.next = prev;

由于单链表的单向性，我们只能通过当前节点查找到下一个节点，而不能查找到上一个节点，为了解决这个问题，可以定义一个变量prev来存放当前节点的上一个节点

在第一个迭代时，头结点的上一个节点应为null，所以prev的初始值为null，在curr即当前节点向后移动之前，应将prev先指向当前节点，之后当前节点再进行移动，这样才能保证prev永远为curr的上一个节点

ListNode prev = null;     //1
ListNode curr = head;     //2
                          //3
curr.next = prev;         //4
prev = curr;              //5
curr = curr.next;         //6

但是这里存在的问题是，在第4行代码执行时，curr的下一个节点已经指向了prev，所以在第6行将curr向后移动时会出现问题

在单链表中，如果将当前节点的next指向其他节点，那么curr原本的后继结点将无法被访问到

因此，可以再次定义一个变量next来暂存当前节点指向下一个节点的指针，该操作应发生在curr将next指向prev，即将当前节点的下一个节点指向当前节点的上一个节点之前完成

ListNode prev = null;
ListNode curr = head,next;

next = curr.next;
curr.next = prev;
prev = curr;
curr = next;

这段代码便是迭代方法的核心代码，接下来通过判断迭代次数来完善代码

迭代次数思路为，在链表不为空的情况下，若curr即当前节点为null时，表示链表中最后一个节点已经完成了指针反转，此时可退出循环，完整代码如下

class Solution {
    public ListNode reverseList(ListNode head) {
        // 若链表为空或链表只存在一个节点，直接返回头结点
        if(head == null || head.next == null) {
            return head;
        }
        // 定义前驱节点，当前节点和后继节点，并将前驱节点初始为null，当前节点初始为head
        ListNode prev = null;
        ListNode curr = head,next;
	    // 当curr不为null时进入循环
        while(curr != null) {
            // 暂存当前节点的后继节点
            next = curr.next;
            // 将当前节点的下一个节点指向前驱节点
            curr.next = prev;
            // 将前驱节点移动到当前节点
            prev = curr;
            // 将当前节点向后移动
            curr = next;
        }
        return prev;
    }
}

递归

链表中的每个指针都牵扯到两个节点，即当前节点和后继节点，可以将整个链表分为多个小链表处理，每次都将当前节点的后继节点指向当前节点

若从前向后处理，后续节点便会失去引用，所以可以从后向前去处理

首先要获取到链表中的最后一个节点，可以使用递归方法来实现

reverseList(head.next);

当head.next指向null时，意味着当前节点便是最后节点，并将该节点返回，作为新的链表头节点

if(head == null || head.next == null) {
    return head;
}
ListNode newHead = reverseList(head.next);

方法栈图解

在每次操作时，需要将后继节点的下一个节点指向当前节点

通过head.next获取后继结点，通过head.next.next可获取后继节点的后继节点

当完成一次指针反转时，将当前节点的下一个节点设为null

if(head == null || head.next == null) {
    return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;

在最后将新的链表头结点返回即可，完整代码如下

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        // 递归寻找最后一个节点，将其设置为新的头结点
        ListNode newHead = reverseList(head.next);
        // 将后继节点的下一位指向当前节点
        head.next.next = head;
        // 将当前节点的后继节点置空
        head.next = null;
        // 返回新的头结点
        return newHead;
    }
}