3

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

这是我想要的输出示例

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 并将每个节点单独添加到末尾是微不足道的，但这对于链表来说感觉不正确。

谁能给我一些关于如何有效地做到这一点的建议

4

2 回答 2

9

你需要做两件事：

  • 将tail.nextfirst设置list为head2nd list。
  • 然后将tail2 nd list重新分配给tail1 st list

所以，这就是你的方法应该是这样的：

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

您最好将此方法命名为extend. 这更清楚地显示了该方法的意图。

于 2013-02-14T11:42:03.197 回答
0

您想将head输入列表添加tail到此列表中。只需将其编写为代码：

public void add(MyList list) 
{
    this.tail.next = list.head;
    this.tail = list.tail;
}
于 2013-02-14T11:43:00.633 回答