题目描述

题目链接:206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

给你单链表的头节点 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

迭代

假设链表为 $1 \rightarrow 2 \rightarrow 3 \rightarrow \varnothing$，我们想要把它改成 $\varnothing \leftarrow 1 \leftarrow 2 \leftarrow 3$。

在遍历链表时，将当前节点的 $\textit{next}$ ​ 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}