Почему следующий код не работает при вставке узла в определенную позицию в связанном списке?

Пожалуйста, взгляните на следующий код и дайте мне знать, что с ним не так? Я пытаюсь вставить узел в заданную конкретную позицию в связанном списке. Нам нужно вернуть ссылку на головной узел после его вставки.

Node InsertNth(Node head, int data, int position) {
    Node newNode = new Node();
    newNode.data = data;

    if(head==null){
        newNode.next = head;
        return newNode;
    }
    Node first = head;

    while(position > 0 && head.next!=null){
        head = head.next;
        position -= 1;
    }

    newNode.next = head;
    head = newNode;
    return first;

}

java algorithm data-structures linked-list
person आनंद    schedule 09.11.2016    source источник
comment
Все проблемы в этих последних 3-х строках. Вы никогда не присваивали newNode чему-либо next.   -  person 4castle    schedule 09.11.2016

Ответы (1)


arrow_upward
1
arrow_downward

Да, что-то не так. После цикла while вы пытаетесь вставить newNode ПЕРЕД head, но это не работает. Строка head=newNode; бесполезна.

Либо вам нужен еще один указатель, указывающий на узел перед head, чтобы вы могли вставить newNode между этими двумя указателями, либо вам нужно остановить цикл while на один шаг раньше и вставить newNode ПОСЛЕ head. Вот второе решение:

 while(position > 1 && head.next!=null){ //0 is replaced by 1 here
    head = head.next;
    position -= 1;
}

newNode.next = head.next;
head.next = newNode;
return first;

[РЕДАКТИРОВАТЬ]

В этом решении вам нужно обработать особый случай, когда position равно 0, добавив следующий код непосредственно перед циклом while:

if(position==0) {
    newNode.next = head.next;
    return newNode;
}
person AhmadWabbi    schedule 09.11.2016
comment
Спасибо. Что делать, если позиция 0 или 1? Это не работает для этого. - person आनंद; 09.11.2016
comment
Позиция 1 работает нормально: цикл вообще не повторяется и newNode вставляется после head, что является правильной позицией 1. Что касается позиции 0, вы правы, она не работает. Вам нужно добавить специальный случай для него. Я изменю ответ соответственно. - person AhmadWabbi; 09.11.2016