面试题24_反转链表.md

面试题 24 ：反转链表

---

leetcode-cn 题目地址

📗difficulty： Easy

🎯Tags：

• 链表

---

1. 题目描述📃

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

样例 1 ：

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

限制：

• 0 <= 节点个数 <= 5000

注意：

• 本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

---

2. 解题思路💡

迭代法

双指针思路。

对于链表的指针操作，可以借助画图来辅助理清指针的变换，容易理解且不容易出错。

巧妙的地方在于 cur = null 的设定。

代码实现

// 迭代法
public ListNode reverseList(ListNode head) {
    ListNode cur = null;
    ListNode pre = head;
    ListNode t = null;
    // 若 head 为 null 则跳过 while 循环，返回 cur = null
    while (pre != null) {
        t = pre.next;
        pre.next = cur;
        cur = pre;
        pre = t;
    }
    return cur;
}

复杂度分析

• 时间复杂度：O(n) 。
• 空间复杂度：O(1) 。

---

以下思路来自于 leetcode-cn 用户 王尼玛 的题解，感谢其详实的分析。

递归解法

代码实现

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode cur = reverseList(head.next);
    head.next.next = head; // 绕回来了
    head.next = null; // 断开指针，防止循环
    return cur;
}

复杂度分析

• 时间复杂度：O(n) 。
• 空间复杂度：O(n) 。

---

3. 总结🎯

相似题目

206. 反转链表

剑指 Offer 06. 从尾到头打印链表

本题考点

• 考察应聘者对链表、指针的编程能力。
• 特别注重考察应聘者思维的全面性以及写出来的代码的鲁棒性。