实现一个不可变的链表（LinkedList）并添加反转功能 -

题目

实现一个不可变的链表（LinkedList）并添加反转功能

信息

类型：问答
难度：⭐⭐

考点

不可变数据结构,递归与尾递归优化,模式匹配,ADT设计

快速回答

实现要点：

使用sealed trait定义链表ADT
通过case object和case class实现空链表和节点
反转方法需支持递归和尾递归两种实现
注意处理边界条件（空链表）

## 解析

原理说明

在Scala中实现不可变数据结构需遵循：1) 所有操作返回新实例 2) 利用递归处理链式结构 3) 使用尾递归避免栈溢出。链表反转的核心是将节点引用方向倒置，通过递归或迭代累积中间结果。

代码实现

// 1. 定义ADT
sealed trait LinkedList[+T]
case object Empty extends LinkedList[Nothing]
case class Node[T](head: T, tail: LinkedList[T]) extends LinkedList[T]

object LinkedList {
  // 2. 普通递归实现（非尾递归）
  def reverseRecursive[T](list: LinkedList[T]): LinkedList[T] = list match {
    case Empty => Empty
    case Node(h, t) => reverseRecursive(t) match {
      case Empty => Node(h, Empty)
      case reversedTail => append(reversedTail, Node(h, Empty))
    }
  }

  // 3. 尾递归优化实现
  def reverseTailRec[T](list: LinkedList[T]): LinkedList[T] = {
    @annotation.tailrec
    def loop(remaining: LinkedList[T], acc: LinkedList[T]): LinkedList[T] =
      remaining match {
        case Empty => acc
        case Node(h, t) => loop(t, Node(h, acc))
      }
    loop(list, Empty)
  }

  // 辅助方法：追加节点
  private def append[T](a: LinkedList[T], b: LinkedList[T]): LinkedList[T] = a match {
    case Empty => b
    case Node(h, t) => Node(h, append(t, b))
  }
}

最佳实践

优先使用尾递归：避免长链表导致的栈溢出，Scala编译器会优化为循环
ADT设计模式：sealed trait + case class确保模式匹配完整性
不可变性：所有操作返回新实例，原始链表保持不变

常见错误

忘记@tailrec注解导致未优化的递归
模式匹配未处理Empty边界情况
在普通递归中直接拼接节点（如Node(h, reverse(t))），导致顺序错误

扩展知识

性能对比：尾递归时间复杂度O(n)，空间复杂度O(1)；普通递归空间复杂度O(n)
Scala标准库实现：scala.collection.immutable.List使用::操作符，其reverse方法采用尾递归
模式匹配优化：编译器会检测sealed trait的子类，确保匹配完整性
类型协变：LinkedList[+T]中的+支持子类型替换（如LinkedList[Dog]可赋值给LinkedList[Animal]）