如何将一个链表附加到另一个链表的末尾？

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时，我希望可以扩展list1而不破坏原始的list2。 我无法想象在不迭代任何内容的情况下如何做到这一点。在add方法中遍历list2并逐个将每个节点添加到末尾是很容易的，但使用链表来做这件事感觉不太对。有人能给我一些关于如何高效地实现这个目标的建议吗？

- Mark Dunne

Answer 1

你需要做两件事情：

• 将第一个列表list的tail.next设置为第二个列表list的head。
• 然后将第二个列表list的tail重新分配给第一个列表list的tail

因此，你的方法应该是这样的：

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

你最好将这个方法命名为extend。这样更清楚地显示了该方法的意图。

- Rohit Jain

---

这让我想起了几年前在我的C/C++课上的一项练习。+1 为怀旧之情（也是因为这是一个好答案 :P）。 - Fritz

我被难倒了。我编写了上面的代码作为一个问题的示例，这个问题是在一个更大的项目中出现的。在那个项目中，我尝试了这个确切的方法，但它不起作用，但是现在看来它起作用了！我想我需要仔细查看我的代码。 - Mark Dunne

@Gamb。我也遇到过同样的情况。那些时候，链表就像是最可怕的话题，让我感到非常困扰。 - Rohit Jain

我知道你已经回答了给出的问题，但我发现原始问题的来源。在我的大型项目中，除了将一个列表添加到另一个列表中，我还希望扩展列表成为一个循环链表。我认为只需要在方法的末尾添加 tail.next = head; 就可以了，但这似乎会导致一切都崩溃。现在两个列表都会变得更长，其中一个的末端在另一个的前面。有任何想法是为什么吗？ - Mark Dunne

那么在这种情况下，解决方案必须是迭代list中的所有节点？ - Mark Dunne

Answer 2

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

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

- Azodious