LeetCode 234回文链表字符串解法超时，求原因解析

1. 字符串拼接的时间开销是核心问题 #

Java里的String是不可变对象，每次执行s = s + head.val或者p = head.val + p时，都会创建一个全新的String对象，并且需要把原字符串的所有字符复制到新对象中，再追加新的字符。假如链表长度是n，那拼接s的总操作次数是1+2+3+...+n = n(n+1)/2，时间复杂度是O(n²)。当遇到LeetCode的大型测试用例（比如n达到10^{5），这种二次复杂度的操作会产生10}10级别的总运算量，直接导致超时。

2. equals方法不是O(1)操作 #

你之前的理解有误：String.equals()需要逐个比较两个字符串的每一个字符，直到发现不匹配的字符或者遍历完所有字符，时间复杂度是O(n)。不过这部分开销和拼接的O(n²)比起来，只是次要因素。

3. 双指针/栈解法的效率优势 #

双指针（找中点+反转后半段）或栈的解法，看似是多循环，但总操作次数是线性的：比如找中点是O(n)，反转后半段是O(n/2)，比较是O(n/2)，总时间复杂度是O(n)。和O(n²)的解法对比，当n=10^5时，O(n)的总运算量只有10^{5级别，和10}10差距巨大，所以这类解法能轻松通过测试用例。

优化后的字符串解法 #

如果想用字符串思路通过测试，可以用StringBuilder替代String，并且避免头部插入（头部插入仍是O(n)每次），改成先拼接成完整字符串再反转比较：

class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val);
            head = head.next;
        }
        String original = sb.toString();
        String reversed = sb.reverse().toString();
        return original.equals(reversed);
    }
}

这个版本的总时间复杂度是O(n)，可以顺利通过所有测试用例。

内容的提问来源于stack exchange，提问作者ARPAN NANDI