拼接后LinkedList对象未独立，求修正append/insert异常问题

我自己实现了一个不依赖Java库的LinkedList类，测试时发现执行concat操作后，对两个链表分别执行append和insert操作，会导致彼此内容互相影响，最终输出结果不符合预期，请求帮忙排查并修正代码。

LinkedList类代码 #

class LinkedList {
    LinkedList.Node head = null;

    int size = 0;
    class Node {
        char value;
        Node next = null;
        public Node(char value){
            this.value = value;
            this.next = null;
        }

        public char getValue() {
            return value;
        }

        public void setValue(char value) {
            this.value = value;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    public void concat(LinkedList otherList) {
        if (otherList == null) {
            return;
        }
        else if (this.head == null) {
            this.head = otherList.head;
            size += otherList.size;
        } else {
            LinkedList.Node current = this.head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = otherList.head;
            size += otherList.size;
        }
    }

    public LinkedList append(char ch) {
        if (head == null) {
            head = new Node(ch);
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = new Node(ch);
        }
        size++;
        return this;
    }

    public static String toString(LinkedList list) {
        String result= "";
        int i= 0;

        while (i < list.length()) {
            result += list.getCharAt(i);
            i++;
        }

        return result;
    }

    public char getCharAt(int position) throws IndexOutOfBoundsException {
        Node current = head;
        for(int nodeIndex = 0; nodeIndex < size; nodeIndex++){
            if(nodeIndex == position) {
                break;
            }
            else{
                current = current.next;

            }
        }

        return current.value;
    }

    public int length() {
        Node temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    public void insert(int position, char ch) throws IndexOutOfBoundsException {
        if (position == size) {
            append(ch);
        } else if (position > size) {
            throw new IndexOutOfBoundsException();
        } else {
            Node newNode = new Node(ch);
            if (head == null) {
                head = newNode;
            } else if (position == 0) {
                newNode.next = head;
                head = newNode;
            } else {
                Node current = head;
                Node previous = null;
                for (int i = 0; i < position; i++) {
                    previous = current;
                    current = current.next;
                }
                newNode.next = current;
                previous.next = newNode;
            }
            size++;
        }

    }
}

Main类代码 #

public class Main {
    public static void main(String[] args) {
        LinkedList list1= new LinkedList();
        LinkedList list2= new LinkedList();

        list1= list1.append('t').append('i').append('n').append('k').append('e').append('r');
        list2= list2.append('b').append('e').append('l').append('l');

        System.out.println(LinkedList.toString(list1)); // tinker correct
        System.out.println(LinkedList.toString(list2)); // bell correct


        list1.concat(list2); // tinkerbell correct

        System.out.println(LinkedList.toString(list1)); // tinkerbell correct
        System.out.println(LinkedList.toString(list2)); // bell correct


        list1.append('s');  // make tinkerbell -> tinkerbells
        list2.insert(3, 'e'); //bell -> belel

        System.out.println(LinkedList.toString(list1)); // printing tinkerbelels - should be tinkerbells  - incorrect
        System.out.println(LinkedList.toString(list2)); // printing belels - should be belel  -  incorrect

    }
}

问题原因 #

问题出在concat方法里：直接把otherList.head挂到当前链表的末尾，导致两个链表共享了同一段节点引用。concat之后list1的末尾和list2的head指向同一个节点链，后续对任意一个链表的修改（比如append或insert）都会直接修改这段共享的节点，造成两个链表内容互相影响。

修复方案 #

修改concat方法，复制otherList的每个节点，创建新的Node对象添加到当前链表，让两个链表的节点完全独立，后续操作就不会互相干扰。

修正后的concat方法代码：

public void concat(LinkedList otherList) {
    if (otherList == null || otherList.head == null) {
        return;
    }
    // 遍历otherList，复制每个节点并添加到当前链表
    Node currentOther = otherList.head;
    while (currentOther != null) {
        this.append(currentOther.value);
        currentOther = currentOther.next;
    }
}

另外原代码中length方法是遍历节点计数，size是手动维护的字段，容易出现不一致。修复后的concat调用append添加节点，append会自动递增size，能保证size和实际节点数一致，避免后续getCharAt或insert方法出错。

验证修复效果 #

修改后运行Main类，输出会符合预期：

• list1.append('s')后变为tinkerbells
• list2.insert(3, 'e')后变为belel
  两个链表的修改不会互相影响，最终输出结果正确。

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