如何反转一个链表？

推荐答案

-- -------------------- ---- -------
----- ---------
    --- -------------- ------ -----------
        -------- - ---
        --------- - ----

--- ----------------- --------- -- ---------
    ---- - ----
    ---- - ----
    ----- -----
        --------- - ---------
        --------- - ----
        ---- - ----
        ---- - ---------
    ------ ----

本题详细解读

问题描述

反转一个单链表。例如，给定链表 1->2->3->4->5，反转后应得到 5->4->3->2->1。

解题思路

反转链表的基本思路是通过遍历链表，逐个改变节点的指向。具体步骤如下：

1. 初始化两个指针：prev 和 curr。prev 初始化为 None，curr 初始化为链表的头节点 head。
2. 遍历链表：在遍历过程中，每次将当前节点 curr 的 next 指针指向 prev，然后将 prev 和 curr 向前移动一步。
3. 终止条件：当 curr 为 None 时，遍历结束，此时 prev 指向新的头节点。
4. 返回结果：返回 prev，即反转后的链表头节点。

代码解析

• ListNode 类定义了链表节点的结构，包含 val 和 next 两个属性。
• reverseList 函数实现了链表的反转：
  • prev 用于保存当前节点的前一个节点。
  • curr 用于遍历链表。
  • next_temp 用于临时保存当前节点的下一个节点，以便在改变 curr.next 后继续遍历。
  • 在循环中，每次将 curr.next 指向 prev，然后更新 prev 和 curr 的位置。
  • 最终返回 prev，即反转后的链表头节点。

时间复杂度

• 时间复杂度为 O(n)，其中 n 是链表的长度。因为需要遍历整个链表一次。
• 空间复杂度为 O(1)，只使用了常数级别的额外空间。