目录

链表反转

链表反转：深入浅出

链表反转是什么？

链表反转，顾名思义，就是将一个链表的节点顺序颠倒过来。例如，原本的链表是1->2->3->4，反转后就变成4->3->2->1。

为什么需要链表反转？

链表反转是链表操作中一个非常基础且常见的操作，它在很多算法和数据结构中都有应用，比如：

链表反转的实现

迭代法

迭代法是实现链表反转最常用的方法。其核心思想是：

  1. 初始化三个指针：
    • prev: 指向当前节点的前一个节点
    • curr: 指向当前节点
    • next: 指向当前节点的后一个节点
  2. 遍历链表：
    • 将 curr 的 next 指针指向 prev，实现反转
    • 将 prev 和 curr 指针都向后移动一位
  3. 返回新的头节点： 遍历结束后，curr 指向新的头节点
func reverseList(head *ListNode) *ListNode {
    // 初始化第一个前驱指针指向null, 即为末端
    var prev *ListNode

    for curr:= head; curr != nil; {
        // 先用临时指针next保存下一个开始位置
        next := curr.Next;
        // 将当前指针指反转
        curr.Next = prev;

        // 移动指针
        prev = curr;
        curr = next;
    }

    return prev;
}

递归法

递归法是一种更加优雅的实现方式。其核心思想是：

  1. 递归终止条件： 当链表为空或只有一个节点时，直接返回。
  2. 递归过程：
    • 递归反转链表的后半部分
    • 将链表的后半部分的头节点的 next 指向当前节点
    • 将当前节点的 next 指向 nullptr
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

链表反转的复杂度分析

总结

链表反转是一个基础且重要的链表操作。通过迭代法和递归法，我们可以实现链表的反转。在选择实现方式时，可以根据具体情况和个人偏好来决定。

想了解更多关于链表反转的细节吗？ 欢迎提出更多的问题，例如：