java - 如何将链表附加到另一个链表的后面？

Question

我已经实现了自己的链表类型的数据结构，但是当我想将一个链表附加到另一个链表而不对任何内容进行迭代时，我遇到了一个问题。

这是我想要的输出示例

public class MyList{

    public static void main(String[] args){
        MyList list1 = new MyList(3);
        MyList list2 = new MyList(4);

        System.out.println(list1);  //0 1 2
        System.out.println(list2);  //0 1 2 3

        list1.add(list2);

        System.out.println(list1);  //0 1 2 0 1 2 3
        System.out.println(list2);  //0 1 2 3
    }

    private class Node{
        public int data;
        public Node next;

        public Node(int data){
            this.data = data;
        }
    }

    public Node head;
    public Node tail;

    public MyList(int length){
        for(int i = 0; i < length; i++){
            add(new Node(i));
        }
    }

    public void add(Node node) {
        if (head == null) {
            //insert first node
            head = node;
            tail = node;
        } else {
            //add node to end
            tail.next = node;
            tail = tail.next;
        }
    }

    //Problem!
    public void add(MyList list) {

    } 

    @Override
    public String toString(){
        String result = "";
        for(Node iter = head; iter != null; iter = iter.next){
            result += iter.data + " ";
        }
        return result;
    }   
}

当 list2 添加到 list1 时，我希望在不破坏原始 list2 的情况下扩展 list1。我看不出如何在不迭代任何东西的情况下做到这一点。在 add 方法中遍历 list2 并将每个节点单独添加到末尾是微不足道的，但这对链表来说感觉不对。

任何人都可以给我一些建议，告诉我如何有效地做到这一点

Answer 1

你需要做两件事:

• 将第一个list的tail.next设置为第二个list的head。
• 然后将2^nd list的tail重新分配给1^{的tail st} 列表

那么，您的方法应该是这样的:

public void add(MyList list) {
    this.tail.next = list.head;
    this.tail = list.tail;
} 

你最好把这个方法命名为extend。这更清楚地表明了该方法的意图。