Учитывая последний узел односвязного списка, как нам найти головной узел

Учитывая последний узел односвязного списка, как нам найти головной узел?

Скажем, учитывая JSON:

{"id": "A", "next": "B"}, {"id": "B", "next": "C"} {"id": "C", "next": "D "} {" id ":" D "," next ": null}

Теперь предположим, что указанное выше не отсортировано, и нам нужно определить элемент HEAD 'A'.


linked-list singly-linked-list
person Sunil Gollapinni    schedule 18.04.2018    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете использовать Array.prototype.find, чтобы найти элемент, который id не является значением next другого объекта в списке. Предполагая действительный непустой односвязный список, должен быть ровно один элемент, который удовлетворяет этому условию (заголовок). Если список пуст, head будет присвоено значение undefined.

const json = '[{"id": "A", "next": "B"}, {"id": "B", "next": "C"},{"id": "C", "next": "D"},{"id": "D", "next": null}]';
const objects = JSON.parse(json);

const head = objects.find( a => ! objects.find( b => a.id === b.next ) );

console.log( head );

person Paul    schedule 18.04.2018
comment
После того, как я опубликовал этот пост, даже я тоже подумал в тех же строках, где головной узел не будет присутствовать ни в одном из следующих атрибутов. Спасибо за быстрый ответ. - person Sunil Gollapinni; 18.04.2018
comment
@Paulpro Как ! в этом работает? Почему не работает с objects.forEach(...);? Я ничего не нашел об этом в Array.prototype.find. - person Bee; 18.04.2018
comment
@DavidMichaelHuber Это просто логический оператор НЕ . Если внутренний find возвращается и объект, тогда ! будет оцениваться как false, иначе он будет оцениваться как true. - person Paul; 18.04.2018
comment
@Paulpro Меня это почему-то смущает. Вы уверены, что он действительно проверяет единственный элемент, который id не является значением next другого объекта в списке? На мой взгляд, он проверяет первый элемент только на предмет отсутствия id как next ни в одном объекте списка. - person Bee; 18.04.2018
comment
@DavidMichaelHuber В этом вы правы, поэтому мой ответ начинается с предположения, что список действительный. Я, вероятно, должен расширить это до предположения, что допустимый односвязный список. Такой элемент может быть только один и должен быть ровно один, поэтому первый элемент, удовлетворяющий условию, будет таким же, как единственный элемент, удовлетворяющий условию. - person Paul; 18.04.2018
comment
@DavidMichaelHuber Я перефразировал свой ответ. - person Paul; 18.04.2018
comment
@Paulpro Большое спасибо за разъяснение этого вопроса! Меня действительно смутило то, что мое понимание вашего объяснения не совпадало с моим пониманием кода, который вы предоставили. - person Bee; 18.04.2018
comment
Нет проблем @DavidMichaelHuber. Извините за первоначальную путаницу. - person Paul; 19.04.2018