java结合两个链表

Question

我有一个关于组合两个链表的问题。基本上，我想将一个链表附加到另一个链表。

这是我的解决方案。有没有更有效的方法来做到这一点而不循环第一个链表？任何建议将不胜感激。

    static Node connect(LinkedList list1, LinkedList list2) {
    Node original = list1.first;
    Node previous = null;
    Node current = list1.first;
    while (current != null) {
        previous = current;
        current = current.next;
    }
    previous.next = list2.first;
    return original;
}

Answer 1

使用list1.addAll(list2)在list1的末尾附加list2。

Answer 2

对于链表，linkedList.addAll（otherlist）似乎是一个非常糟糕的选择。

linkList.addAll的java api版本开始：

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    Object[] a = c.toArray();

因此，即使您有2个链表，第二个链表也会转换为数组，然后重新构成单个元素。这比合并2个数组更糟糕。

Answer 3

我想这是你自己的链表实现？只有一个指向下一个元素的指针，最后追加的唯一方法是遍历第一个列表的所有元素。

但是，您可以存储指向最后一个元素的指针，以使此操作在恒定时间内运行（只需记住将新列表的最后一个元素更新为添加列表的最后一个元素）。

Answer 4

最好的方法是将第二个列表附加到第一个列表。

1. Create a Node Class.

2. Create New LinkedList Class.

public class LinkedList<T> {

        public Node<T> head = null;

        public LinkedList() {}

        public void addNode(T data){
            if(head == null) {
                head = new Node<T>(data);
            } else {
                Node<T> curr = head;
                while(curr.getNext() != null) {
                    curr = curr.getNext();
                }
                curr.setNext(new Node<T>(data));
            }
        }

        public void appendList(LinkedList<T> linkedList) {
            if(linkedList.head == null) {
                return;
            } else {
                Node<T> curr = linkedList.head;
                while(curr != null) {
                    addNode((T) curr.getData());
                    curr = curr.getNext();
                }
            }
        }
}

3. In the Main function or whereever you want this append to happen, do it like this.

LinkedList<Integer> n = new LinkedListNode().new LinkedList<Integer>();
    n.addNode(23);
    n.addNode(41);
LinkedList<Integer> n1 = new LinkedListNode().new LinkedList<Integer>();
    n1.addNode(50);
    n1.addNode(34);
n.appendList(n1);

我喜欢这样做，所以你不需要传递这两个并在第一个LinkedList中再次循环。

希望有所帮助