вставка в односвязный список

Question

Подскажите пожалуйста, как вставить один односвязный список в другой, начиная с индекса.

Я понимаю то, что если будет вставка второго списка в первый начиная с хвоста, то хвост мы поменяем но конец второго списка Что должна принимать функция, реализующая этот метод: только индекс? Нужно ли в методе создавать новый третий список, который будет содержать первый и второй или можно в первый просто вставить во второй?

class Node{
    constructor(value,next=null) {
        this.value=value
        this.next=next
    }
}

class LinkedList {
    constructor() {
        this.head = null
        this.tail = null
    }

Моя нерабочая реализация:

 function insert(index){

        let currentNode=list.head
        let newNode=new(Node)
        while (currentNode.next){
            --index
            currentNode=currentNode.next
            if (index===0){
                let curNode2=list2.head
                while(curNode2.next){
                    newNode.value=curNode2.value
                    newNode.next=curNode2.next
                    curNode2.next=newNode
                }
            }
        }
    }

пример входных данных:

односвязный список 1: head 0 1 2 tail

односвязный список 2: head A B C tail

пример выходных данных:

вызываем function insert(1)

результат: односвязный список 1 становится: head 0 1 A B C 2 tail

Answer 1

функция size() возвращает размер списка

реализация:

 function insert(index) {
    
        if (list.head === null || list2.head === null || index > list.size()) return null
    
        if (index > 0 && index < list.size()) {
    
            let currentNode = list.head
    
            for (let count = 0; count != index - 1; count++) {
                currentNode = currentNode.next
            }
    
            let tempNode = currentNode.next
    
            currentNode.next = list2.head
    
            currentNode = list.head
    
            while (currentNode.next) {
                currentNode = currentNode.next
            }
            currentNode.next = tempNode
        }
    
        if (index === 0) {
            let currentNode = list2.head
            while (currentNode) {
                list.insertBefore(index, currentNode.value)
                currentNode = currentNode.next
                ++index
            }
        }
    
        if (index===list.size()){
    
            let currentNode=list2.head
    
            while (currentNode){
                list.append(currentNode.value)
                currentNode=currentNode.next
            }
        }
    }

Answer 2

Ваша реализация не работает потому что вы создаёте новый узел newNode и затем помещаете в него все значения из второго списка. Есть ещё недостатки, но этого достаточно, чтобы написать новое решение с нуля.

Разностные списки не популярны в русском сообществе, даже в Википедии нет перевода. Это удобная структура, если вам нужно соединять списки вместе за константное время.

Я предполагаю, что insert – метод класса LinkedList. Тогда он принимает два параметра: insert(index, that). index – место вставки, that – список LinkedList, который вставляется.

Для удобства тестирования я поменял конструктор и добавил итератор:

class Node {
    constructor(value, next = null) {
        this.value = value;
        this.next = next;
    }
}

class LinkedList {
    constructor(node = null) {
        this.head = node;
        this.tail = node;
    }

    insert(index, that) {
        if (this.head === null) {
            this.head = that.head;
            this.tail = that.tail;
        } else if (that.head === null) {
        } else {
            if (index === 0) {
                that.tail.next = this.head;
                this.head = that.head;
            } else {
                let insert_after = this.head;
                for (let i = 1; i < index; ++i) {
                    insert_after = insert_after.next;
                }
                if (insert_after === this.tail) {
                    this.tail = that.tail;
                } else {
                    that.tail.next = insert_after.next;
                }
                insert_after.next = that.head;
            }
        }
    }

    [Symbol.iterator]() {
        let node = this.head;
        const tail = this.tail;
        let done = node === null;
        return {
            next() {
                if (done) {
                    return {value: undefined, done};
                }
                const value = node.value;
                done = node === tail;
                node = node.next;
                return {value, done: false};
            }
        };
    }
}


for (let i = 0; i < 4; ++i) {
    const list1 = new LinkedList(new Node('1'));
    list1.insert(1, new LinkedList(new Node('2')));
    list1.insert(2, new LinkedList(new Node('3')));

    const list2 = new LinkedList(new Node('A'));
    list2.insert(1, new LinkedList(new Node('B')));
    list2.insert(2, new LinkedList(new Node('C')));

    list1.insert(i, list2);

    console.log('---------------');
    for (const v of list1) {
        console.log(v);
    }
}

БЛОГ НА HUSL

вставка в односвязный список

Ответы (2 шт):