Java中局部链表可被方法修改，局部字符串却不行？（LeetCode872相关）

问题背景 #

在解决LeetCode 872题时，最初使用LinkedList的解法可以正常运行：

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        LinkedList<Integer> l1 = new LinkedList<>();
        LinkedList<Integer> l2 = new LinkedList<>();
        traverse(root1,l1);
        traverse(root2, l2);
        if(l1.size()!=l2.size())
            return false;
        for(int i=0;i<l1.size();i++)
            if(l1.get(i)!=l2.get(i))
                return false;
        return true;
        
    }
    public void traverse(TreeNode node, LinkedList ll){
        if(node==null)
            return;
        if(node.left==null&&node.right==null)
        {
            ll.add(node.val);
            return;
        }
        traverse(node.left,ll);
        traverse(node.right,ll);
    }
}

之后尝试用String替代LinkedList，将叶子节点值拼接成字符串后用.equals比较，却发现最终比较的是空字符串，解法失败：

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        String s1 = "";
        String s2 = "";
        traverse(root1,s1);
        traverse(root2,s2);
        return s1.equals(s2);
        
    }
    public void traverse(TreeNode node, String s){
        if(node==null)
            return;
        if(node.left==null&&node.right==null)
        {
            s = s+node.val;
            return;
        }
        traverse(node.left,s);
        traverse(node.right,s);
    }
}

即使换成StringBuilder也无法解决，只有将字符串设为类全局变量才可行。核心疑问是：同样作为leafSimilar方法的局部变量，为什么LinkedList能被traverse方法修改，而String/StringBuilder却不行？

核心差异解析 #

1. Java的参数传递本质：值传递 #

Java中所有参数传递都是值传递，但传递的"值"分两种情况：

• 基本数据类型：传递变量的数值副本；
• 引用数据类型：传递对象的内存地址副本。

2. LinkedList的修改逻辑 #

LinkedList是可变引用类型，当你把l1传给traverse方法时，传递的是l1指向的链表对象的内存地址副本。在traverse里调用ll.add(node.val)，是通过这个地址副本找到原链表对象，直接修改对象内部的元素集合——原方法中的l1和方法内的ll指向同一个对象，所以修改会同步反映到原变量上。

3. String的修改逻辑 #

String是不可变引用类型，执行s = s + node.val时，并没有修改原来的空字符串对象，而是创建了一个新的String对象，并让方法内的局部变量s指向这个新对象。但原方法中的s1仍然指向最初的空字符串，因为传递的地址副本被重新赋值后，不会影响原变量的指向。

4. StringBuilder的误区 #

你提到换成StringBuilder也不行，大概率是写法错误。如果直接对传入的StringBuilder调用append方法，是可以修改原对象的，正确写法如下：

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        traverse(root1,s1);
        traverse(root2,s2);
        return s1.toString().equals(s2.toString());
        
    }
    public void traverse(TreeNode node, StringBuilder s){
        if(node==null)
            return;
        if(node.left==null&&node.right==null)
        {
            s.append(node.val);
            return;
        }
        traverse(node.left,s);
        traverse(node.right,s);
    }
}

append是直接修改StringBuilder对象内部的字符序列，没有创建新对象，方法内的地址副本指向的还是原对象，所以修改会同步到原方法的变量中。

本质总结 #

• LinkedList和StringBuilder是可变引用类型：方法中通过地址副本操作的是原对象的内部状态，修改会同步；
• String是不可变引用类型：任何修改都会创建新对象，方法内的变量指向变更不会影响原方法的变量。

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