如何将链接列表附加到另一个链接列表？

Question

我已经实现了自己的Linked List类型的数据结构,但是当我想将一个链表附加到另一个链接列表而不迭代任何东西时,我遇到了一个问题.

这是我想要的输出示例

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

你需要做两件事:

• 设置tail.next第一list至head第二的list.
• 然后重新分配tail2的^第二 list到tail的1 ^日 list

所以,这就是你的方法应该是这样的:

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

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