Ява объединить два связанных списка

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

Для связанных списков схоже, что linkList.addAll (otherlist) - очень плохой выбор.

Начинается Java-API-версия файла connectedList.addAll:

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

поэтому, даже если у вас есть 2 связанных списка, второй преобразуется в массив, а затем перестраивается в отдельные элементы. Это хуже, чем просто объединение двух массивов.

Answer 2

Используйте list1.addAll(list2) для добавления списка 2 в конец списка 1.

Answer 3

Я полагаю, это ваша собственная реализация связанного списка?Имея только указатель на следующий элемент, единственный способ добавить в конце - это пройти все элементы первого списка.

Однако вы можете сохранить указатель на последний элемент, чтобы эта операция выполнялась впостоянное время (просто не забудьте обновить последний элемент нового списка, чтобы он стал последним элементом добавленного списка).

Answer 4

Лучший способ - добавить второй список в первый список.

1. Создайте класс узла.

2. Создать новый класс LinkedList.

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. В функции Main или там, где вы хотите, чтобы это добавление происходило, сделайте это следующим образом.

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.

Надеюсь, это поможет