Вставьте узел в отсортированный связанный список целых чисел, так что список все еще остается отсортированным с конечными членами для следующего

Question

В Java как бы вы написали метод для вставки узла в отсортированный связанный список целых чисел, чтобы список все еще оставался отсортированным, если все узлы имеют конечную переменную-член для следующего, чтобы вы не могли их изменить?

Answer 1

Когда следующая ссылка окончательна:

Единственный теоретический способ - добавить новый узел перед списка и переместить данные:

void insertSorted(MyList list, int data) {
    list.head = new Node(0, list.head); // Insert in front;
    Node prior = list.head;
    // Invariant condition: prior points to a node (not null) and soon data >= prior.data
    Node current = prior.next;
    while (current != null) {
        if (data < current.data) {
            break;
        }
        prior.data = current.data; // Shift smaller
        prior = current;
        current = current.next;
    }
    prior.data = data;
}

insert:      d
list.head:   a ; b ; c ; e ; f ; g
--------------------------------------
list.head:   X ; a ; b ; c ; e ; f ; g
             a <-´   |   |
                 b <-´   |
                     c <-´
                         d

Это был вопрос для интервью? Кажется, так академи c.