链表--206. 反转链表/easy

1、题目

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

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

2、题目分析

反转链表，主要分2步完成，1是反转，2是迭代。

反转就是将当前节点的后节点指针 指向 前节点（需先暂存原来的后节点，否则会导致后节点丢失）。

迭代就是当前节点的指针 指向 原来的后节点，前节点指针 指向 当前节点。

3、解题步骤

1、反转（①先暂存后节点，②再将后节点指针 指向 前节点）
2、往后迭代（①先将前节点指针 指向 当前节点，②再将当前节点指针 指向 后节点，进入下一循环）

4、复杂度最优解代码示例

    public ListNode reverseList(ListNode head) {
        // 初始化前节点为null
        ListNode pre = null;
        while (head != null) {
            // 1、反转
            // 1.1 暂存后节点
            ListNode next = head.next;
            // 1.2 后节点指针=》前节点
            head.next = pre;

            // 2、往后迭代
            // 2.1 前节点=》当前节点
            pre = head;
            // 2.2 当前节点=》后节点
            head = next;
        }
        // 踩坑：循环到head == null截止，故返回是pre，而不是head。（head恒等于null）
        return pre;
    }

5、抽象与扩展

反转链表在现实生活中的一个应用场景是：在一个音乐播放器中，有一个播放列表，列表中的每首歌曲都有一个指向下一首的指针，表示这首歌曲播放完后应该播放哪首歌。现在我们需要将这个播放列表进行反转，即让最后一首歌成为第一首，以此类推。这时，我们可以使用反转链表的方法来实现。

反转链表适用于链表结构存储的数据，进行正序展示、或逆序展示。