C#链表反转详解（从零掌握迭代与递归两种实现方式）

什么是链表？

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中不是连续存储的。

在 C# 中，我们通常这样定义一个单向链表节点：

public class ListNode{    public int val;    public ListNode next;    public ListNode(int x)    {        val = x;        next = null;    }}

方法一：迭代法反转链表（推荐初学者掌握）

迭代法 是通过循环逐步改变每个节点的指针方向，从而实现整个链表的反转。这种方法空间复杂度为 O(1)，效率高且易于理解。

思路：

• 使用三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点）
• 遍历链表，每次将 curr.next 指向 prev
• 然后移动三个指针，继续下一轮

下面是 C# 实现代码：

public ListNode ReverseListIterative(ListNode head){    ListNode prev = null;    ListNode curr = head;    while (curr != null)    {        ListNode next = curr.next;  // 保存下一个节点        curr.next = prev;           // 反转当前节点的指针        prev = curr;                // 移动 prev 到当前节点        curr = next;                // 移动 curr 到下一个节点    }    return prev; // prev 现在是新的头节点}

这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常适合处理大型链表。

方法二：递归法反转链表（优雅但需理解递归）

递归法 利用函数调用栈来“记住”之前的节点，从而在回溯过程中完成反转。虽然代码更简洁，但对初学者可能稍显抽象。

思路：

• 递归到链表末尾（最后一个节点）
• 在回溯时，将当前节点的下一个节点的 next 指向自己
• 同时将当前节点的 next 设为 null，避免环

C# 递归实现如下：

public ListNode ReverseListRecursive(ListNode head){    // 基础情况：空链表或只有一个节点    if (head == null || head.next == null)    {        return head;    }    // 递归反转后续部分，返回新的头节点    ListNode newHead = ReverseListRecursive(head.next);    // 反转当前连接    head.next.next = head;  // 让下一个节点指向自己    head.next = null;       // 断开原来的连接    return newHead; // 返回新的头节点}

递归方法的时间复杂度同样是 O(n)，但空间复杂度为 O(n)，因为递归调用会占用系统栈空间。

两种方法对比

总结

无论是使用 链表反转迭代 还是 C#链表递归反转，你都已经掌握了 C# 中处理链表反转的核心技巧。建议初学者先熟练掌握迭代法，再尝试理解递归的精妙之处。

掌握这些 数据结构C#教程 中的基础算法，不仅能提升你的编程能力，还能为未来的面试和项目开发打下坚实基础！

动手试试吧！创建一个链表，分别用两种方法反转它，观察输出结果是否一致。实践是最好的老师！