递归判链表回文遇栈溢出，求Dart相关问题及最优解法

1. 递归栈溢出的原因 #

你的递归代码存在两个核心问题：

• 递归深度超标：每次递归都会处理链表的剩余部分，对于长度为n的链表，递归深度达到O(n)。当n足够大时（比如10^4级别），嵌套调用层数会超过Dart虚拟机的栈容量上限，直接触发栈溢出。
• 逻辑错误：代码仅比较当前链表的头节点和尾节点，随后递归处理head.next，但并没有真正移除已比较过的尾节点——比如原链表是[1,2,2,1]，第一次比较1和1后，递归处理[2,2,1]，此时尾节点仍是1，和头节点2比较会直接返回false，逻辑完全错误。此外，每次递归都要遍历整个链表找尾节点，时间复杂度为O(n²)，大测试用例不仅会栈溢出，还会超时。

2. Dart的递归深度查询 #

Dart没有固定的官方递归深度上限，该数值与运行环境（如Dart VM、Flutter、Web编译）相关，通常在几千到一万左右。你可以通过以下代码自行测试当前环境的上限：

int depth = 0;

void measureDepth() {
  depth++;
  measureDepth();
}

void main() {
  try {
    measureDepth();
  } catch (_) {
    print("当前环境递归深度上限: $depth");
  }
}

3. 更高效的解法（时间O(n)，空间O(1)） #

最优解法是快慢指针+反转链表，无需额外存储整个链表，也不会出现栈溢出问题：
步骤：

• 快慢指针找中间节点：慢指针每次走1步，快指针每次走2步，快指针走到末尾时，慢指针刚好处于链表中间位置。
• 反转慢指针之后的后半部分链表。
• 同时遍历前半部分和反转后的后半部分，逐一比较节点值。
• （可选）将反转的后半部分转回原状态，恢复链表结构。

Dart代码实现：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  bool isPalindrome(ListNode? head) {
    if (head == null || head.next == null) return true;
    
    // 1. 快慢指针找中间节点
    ListNode? slow = head;
    ListNode? fast = head;
    while (fast?.next != null && fast?.next?.next != null) {
      slow = slow?.next;
      fast = fast?.next?.next;
    }
    
    // 2. 反转后半部分链表
    ListNode? reversedHalf = reverseList(slow?.next);
    
    // 3. 比较前半部分和反转后的后半部分
    ListNode? p1 = head;
    ListNode? p2 = reversedHalf;
    bool isPalin = true;
    while (p2 != null) {
      if (p1?.val != p2.val) {
        isPalin = false;
        break;
      }
      p1 = p1?.next;
      p2 = p2.next;
    }
    
    // 4. （可选）恢复原链表
    slow?.next = reverseList(reversedHalf);
    
    return isPalin;
  }
  
  // 辅助函数：反转链表
  ListNode? reverseList(ListNode? head) {
    ListNode? prev = null;
    ListNode? current = head;
    while (current != null) {
      ListNode? nextTemp = current.next;
      current.next = prev;
      prev = current;
      current = nextTemp;
    }
    return prev;
  }
}

该方法时间复杂度为O(n)，仅遍历链表三次（找中间、反转、比较），空间复杂度为O(1)，完全适配所有测试用例。

内容的提问来源于stack exchange，提问作者tri-ethylEther