反转链表 | LeetCode-206 | 递归 | 递归法 | 迭代法

二分查找你学废了吗？快来看看这道题如何使用二分查找解决吧!

---

LeetCode链接：206. 反转链表

---

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 双指针(迭代法)

class Solution {
    public ListNode reverseList(ListNode head) {
        // pre 用于存储当前节点的前一个节点，初始化为 null
        ListNode pre = null;
        // cur 用于遍历链表，初始化为头节点
        ListNode cur = head;
        
        // 遍历链表，直到 cur 变为 null
        while (cur != null) {
            // 暂存当前节点的下一个节点
            ListNode temp = cur.next;
            // 将当前节点的 next 指针指向前一个节点，实现反转
            cur.next = pre;
            // 更新 pre 为当前节点
            pre = cur;
            // cur 前进到下一个节点
            cur = temp;
        }
        
        // 返回反转后的链表的新头节点，即原链表的最后一个节点
        return pre;
    }
}

2.2 递归法

class Solution {
    // 反转单链表的主函数
    public ListNode reverseList(ListNode head) {
        // 调用辅助函数进行递归反转，初始调用时前一个节点为 null，当前节点为头节点
        return reverse(null, head);
    }

    // 递归函数，用于反转链表
    public ListNode reverse(ListNode pre, ListNode cur) {
        // 确定终止条件：当当前节点为 null 时，返回前一个节点作为新头节点
        if (cur == null) return pre;

        // 保存当前节点的下一个节点
        ListNode next = cur.next;
        // 将当前节点的 next 指针指向前一个节点，实现反转
        cur.next = pre;

        // 递归调用自身，将当前节点作为前一个节点，将下一个节点作为当前节点
        return reverse(cur, next);
    }
}