Часть 2 из серии статей о структурах данных с помощью JavaScript
В моей последней статье мы создали односвязный список с помощью JavaScript с функциями push, pop, shift и unshift. Проверьте это здесь, если вы еще не знакомы с этим.
В этой статье мы рассмотрим, как перевернуть список. Я решил взять эту функцию как отдельную статью, так как слышал, что это частый вопрос интервью. Давайте приступим к делу.
Во-первых, у вас должен быть настроен класс для создания списка, класс для создания узла и метод push для добавления узлов в список. Это будет выглядеть примерно так.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
let newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
Реверсирование односвязного списка на месте
Отсюда давайте добавим обратный метод. Вместо того, чтобы создавать новый список, мы будем менять его местами.
Первым делом поменяем местами голову и хвост. Мы можем сделать это, создав переменную узла для хранения текущей головы. Затем установите голову как хвост, а хвост - как переменную узла, в которую мы сохранили голову.
reverse() {
let node = this.head;
this.head = this.tail;
this.tail = node;
Затем мы напишем цикл for для обхода каждого узла в списке. Старая голова уже сохранена как переменная с именем node. Кроме того, нам нужно будет создать две другие переменные, чтобы отслеживать предыдущее и следующее значение.
reverse() {
let node = this.head;
this.head = this.tail;
this.tail = node;
let prev = null;
let next;
В цикле for сначала сохраните node.next после следующей переменной (нам нужно сохранить эту переменную, чтобы мы могли получить к ней доступ в цикле). Затем присвойте node.next предыдущее значение (это меняет список).
reverse() {
let node = this.head;
this.head = this.tail;
this.tail = node;
let prev = null;
let next;
for(let i = 0; i < this.length; i++) {
next = node.next;
node.next = prev;
Наконец, мы сдвинем значение узла и предыдущее значение на единицу. Все, что нам нужно сделать, это установить предыдущий как узел, а узел как следующий. В конце цикла мы вернем список, вернув this.
reverse() {
let node = this.head;
this.head = this.tail;
this.tail = node;
let next;
let prev = null;
for(let i = 0; i < this.length; i++) {
next = node.next;
node.next = prev;
prev = node;
node = next;
}
return this;
}
Окончательный код, включая методы, добавленные из предыдущей статьи, будет выглядеть так.
Теперь вы можете создать список, создав новый экземпляр класса SinglyLinkedList и вставив данные в список. Если вы вызовете обратный метод в списке, вы успешно перевернете односвязный список!
Спасибо за внимание! Если вам интересно узнать больше, я рекомендую пройти курс Удеми Кольта Стила Мастер-класс по алгоритмам JavaScript и структурам данных.
Ознакомьтесь с третьей частью серии статей, в которой мы рассмотрим стеки и очереди.
