Leetcode 234. 回文链表，字符串解法给出超时错误，谁能解释一下为什么吗？

Question

这是我给出的解决方案。

class Solution {

    public boolean isPalindrome(ListNode head) {
       String s= "";
       String p= "";
        while(head != null){
            s= s+head.val;
            p = head.val+p;
            head = head.next;
        }
        return s.equals(p);
    }
}

我可以理解我正在字符串池中创建多个字符串。但它不显示内存超出。它显示“测试用例已通过，但花费的时间太长。”

有人可以解释一下为什么会超过时间限制，而所有其他解决方案都至少有两个循环吗？无论是两个指针解决方案还是列表解决方案或堆栈解决方案。

我希望它能够正常运行，因为我只是使用一个循环来创建反向字符串和普通字符串，并且据我所知 equals 是一个 O(1) 过程。那么如何超过时间限制呢？

Answer 1

我只是使用一个循环来创建反向字符串和普通字符串，据我所知 equals 是一个 O(1) 过程。

事实并非如此。

s+head.val

和

head.val+p

都是需要访问所涉及字符串中每个字符的表达式，因此它们的时间复杂度为O(𝑛)，其中𝑛分别是

s

或

p

的当前大小。

为了改进这一点，请使用

StringBuffer

，其

append

方法的摊余时间复杂度为 O(1)。不要在循环中构建

p

，仅构建

s

，并在循环结束时反转

s

：

class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuffer s = new StringBuffer();
        while (head != null) {
            s.append(head.val);
            head = head.next;
        }
        return s.toString().equals(s.reverse().toString());
    }
}

这具有最佳的——O(𝑛)——时间复杂度。

请注意，如果节点的值可以有多个字符（当转换为字符串表示形式时），这将不起作用。但由于代码挑战在其约束部分中指定这些值是单位数字，因此这不是问题。