Как реализовать связанные списки в JavaScript (часть 2)
Это продолжение Части 1.
Добро пожаловать назад! Приступим к решению некоторых проблем.
Я использую head для обращения к связанному списку. Поскольку мы обращаемся к списку через указатель головы, это имеет смысл в моей… голове (😅).
Я буду использовать эти классы повторно, поэтому напишу их здесь, чтобы не загромождать остальные записи.
class Node {
constructor(data, next) {
this.data = data;
this.next = null;
}
};
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
};
Вот как мы можем перевернуть связанный список.
1. Создайте переменную «текущую» и «предыдущую», равную нулю.
2. назначить напор на текущий
3. назначьте ссылку следующего главы на голову (я пытаюсь сказать, что узел после главы помечается как голова)
4. Теперь сделайте текущее значение рядом с предыдущим - фактически, повернув его на ноль (представьте, что поверните точку отсчета на 180 градусов).
5. теперь назначьте текущий предыдущему (теперь переместите метку с нуля на узел, к которому он подключается)
6. Теперь продолжайте делать это, пока не дойдете до конца связанного списка.
const reverseList (head) => {
let previous = null;
let current;
while (head != null) {
current = head;
head = head.next;
current.next = previous;
previous = current;
}
return current;
}
Распечатать список в обратном порядке довольно просто. Есть несколько способов сделать это, но мне нравится простой рекурсивный вызов.
1. скажите программе, чтобы она закончилась, если мы не в начале
2. рекурсивно вызвать функцию reversePrint на следующем узле.
3. и данные печатающей головки
const reversePrint = (head) => {
if (!head) {
return;
}
reversePrint(head.next);
console.log(head.data);
}
По сути, мы просим программу запустить функцию на самой себе. Он проходит через первый узел. Очевидно, что осталось больше связанного списка, поэтому он не «возвращает» / не останавливает выполнение функции, а отправляет управление следующему узлу, пока мы не дойдем до конца. Теперь он разворачивается и начинает выполнение console.log, так что он печатает последний, второй последний… полностью до начала. Рекурсия не имеет большого смысла, но я учусь ее использовать, и она действительно помогает немного упростить программы.
Следующий интересный. Мне потребовалось время, чтобы сообразить, и когда я это понял, я почувствовал тяжесть с плеча. Давайте попробуем получить значение узла из определенной позиции, считая назад от хвостового узла.
Самым очевидным, что я задумал, было просмотреть список и сохранить значения в массиве, а затем получить ответ. Но тогда я почувствовал, что было бы такой тратой использовать больше памяти, а также отговоркой, если бы я не понимал, как правильно манипулировать связанными списками. Итак, вот что я придумал.
Предположим, список из 6 узлов. Если мы хотим, чтобы значение узла было 2 от хвоста, имеет смысл пройти весь путь до конца, а затем вернуться к 2 оттуда. Также имеет смысл иметь две переменные, идущие только вперед, чем одну переменную, идущую вперед и затем назад. Мы разносим две переменные друг от друга через итерацию так, чтобы они стали равными расстоянию от хвостового узла до узла, который мы ищем. Мы делаем это, используя индекс, инициированный до 0. Итак, когда текущий узел находится на 2, мы начинаем увеличивать индекс и назначать его следующий узел для результата - разница между текущим и результатом равна 2, что при перемещении в конец списка дает нам ответ.
1. создайте индекс переменной и инициализируйте его нулем
2. Создайте переменные current и result и инициализируйте их заголовком.
3. назначить его следующий узел текущему
4. продолжайте увеличивать индекс за каждый ход и каждый раз, когда он больше, чем позиция от хвоста, присваивайте свой следующий узел результату. -
5. проделайте это до конца списка и затем распечатайте данные результата.
const nodeFromTail = (head, positionFromTail) => {
let index = 0;
let current = head;
let result = head;
while (current != null) {
current = current.next;
if (index++ > positionFromTail) {
result = result.next
}
}
return result.data;
}
Сравнение двух связанных списков после этого становится довольно простым делом.
1. проверьте первый узел, если данные не равны, значит, это не дубликат.
2. Теперь перейдите к следующему узлу и повторите первый шаг.
3. Если мы прошли итерацию по списку, и один из списков не дошел до конца, то они не дублируются.
const compareLists (head1, head2) {
while (head1 != null && head2 != null) {
if (head1.data != head2.data) {
return false;
}
head1 = head1.next;
head2 = head2.next;
}
if (head1 != null || head2 != null) {
return false;
}
return true;
}
Объединение двух отсортированных списков - это создание условия if и другого вызова рекурсии.
1. если один из списков пуст, возвращается другой.
2. Если данные узла list2 больше, чем list1, то запустите ту же самую функцию на следующем узле list1. Поэтому, когда данных на самом деле больше, они будут отправлены
3. То же самое для list2.
const mergeLists (head1, head2) {
if (head1 == null || head2 == null) {
return (head1 == null) ? head2 : head1;
}
if (head1.data < head2.data) {
head1.next = mergeLists(head1.next, head2)
return head1;
} else {
head2.next = mergeLists(head1, head2.next);
return head2;
}
}
Теперь вопрос в том, что если у вас есть два списка и несколько одинаковых точек данных, то в списке будут все эти дубликаты. Итак, теперь мы пытаемся удалить повторяющиеся узлы значений из списка.
1. если первый или последующий пусты, то возвращаем головной узел
2. если данные не равны данным в следующем, тогда назначьте его следующий узел на голову
3. в противном случае назначьте его следующий узел следующему узлу головы, по сути, пропуская дублированный
4. запустить цикл по всему списку
const removeDuplicates = (head) => {
if (head == null || head.next == null) return head;
let root = head;
while (head.next != null) {
if (head.data != head.next.data) {
head = head.next;
} else {
head.next = head.next.next;
}
}
return root;
}
Я хочу решить одну последнюю очень интересную проблему, прежде чем я ее прекращу. Чтобы попасть в середину связанного списка, есть два способа:
во-первых, выполнить линейную итерацию по списку, разрезать его пополам и затем вернуться назад, что было бы медленным с очень большими наборами данных. И, во-вторых, иметь 2 указателя, один из которых перемещается с шагом 1, а другой - с шагом 2. К тому времени, когда второй указатель достигнет конца, первый указатель будет посередине.
const findMiddle = (head) => {
let slow_ptr = head;
let fast_ptr = head;
if (head == null) return;
if (head != null) {
while (fast_ptr != null && fast_ptr.next != null) {
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
}
return slow_ptr.data;
}
Это все, что касается основ. Я решу еще несколько проблем и напишу еще несколько заметок как можно скорее. ✌️
Больше контента на plainenglish.io
