【迭代, 递归】反转链表

题目

206. 反转链表

剑指 Offer 24. 反转链表

剑指 Offer II 024. 反转链表

---

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题

方法一：递归

思路

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：
输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：

那么输入 reverse(head) 后，会在这里进行递归：

ListNode newHead = reverse(head.next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：

这个 reverse(head.next) 执行完成后，整个链表就成了这样：

并且根据函数定义，reverse() 函数会返回反转之后的头结点，我们用变量 newHead 接收了。
现在再来看下面的代码：

head.next.next = head;

接下来：

head.next = null;
return last;

神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：

1. 递归函数要有 base case，也就是这句：

   if (head == null || head.next == null) return head;
   

   意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

2. 当链表递归反转之后，新的头结点是 newHead，而之前的 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;
    }
}

方法二：迭代

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode curr = head, newNext = null, newPrev;
        while (curr != null) {
            newPrev = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        return newNext;
    }
}