Связанные списки могут показаться не самой захватывающей темой в мире, но они являются важной частью набора инструментов программиста.
На собеседовании вы можете рассчитывать на проверку вашего понимания связанных списков и способов их эффективного использования. Если вас попросят реализовать связанный список с нуля или объяснить, как вы будете использовать его для решения конкретной проблемы... Так что не спите на связанных списках — они могут быть не самой яркой темой, но они являются важной частью. путешествия по кодированию.
Что такое связанный список?
Связный список — это линейная структура данных, в которой хранится последовательность элементов. Каждый элемент (называемый узлом) состоит из значенияи ссылки на следующий элемент в списке. Элементы в связанном списке связаны с помощью указателей.
Первый элемент связанного списка называется головой, а последний элемент называется концом. Голова — это начальная точка для обхода списка, а хвост — конечная точка.
Реализация связанного списка
В JavaScript связанный список может быть реализован с использованием объектов и указателей. Каждый объект представляет узел в списке и имеет два свойства: свойство «value» для хранения значения узла и свойство «next» для хранения ссылки на следующий узел в списке.
Вот простой пример связанного списка с методом, который добавляет элемент в хвост в JavaScript:
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
addToTail(value) {
const newNode = { value, next: null };
if (!this.head) {
this.head = newNode;
} else {
this.tail.next = newNode;// adding new node always to the end.
}
this.tail = newNode;
}
}
Этот блок кода можно использовать как:
const list = new LinkedList(); list.addToTail(1); list.addToTail(2); list.addToTail(3);
Этот конкретный код создаст связанный список с тремя узлами. head объекта списка будет указывать на первый узел в списке (со значением 1), а хвост будет указывать на последний узел в списке ( со значением 3). Результат, который мы можем наблюдать на каждом этапе, будет следующим:
LinkedList { head: null, tail: null }
LinkedList {
head: { value: 1, next: null },
tail: { value: 1, next: null }
}
LinkedList {
head: { value: 1, next: { value: 2, next: null } },
tail: { value: 2, next: null }
}
LinkedList {
head: { value: 1, next: { value: 2, next: [Object] } },
tail: { value: 3, next: null }
}
Проблемы от LeetCode
Я выбрал группу задач, связанных с использованием и пониманием связанных списков. Прежде чем пытаться решить эти проблемы, давайте уделим некоторое время тому, чтобы понять вопросы и то, что от нас требуется. Как только мы хорошо разберемся в проблемах, мы сможем разработать решения, используя связанные списки.
206. Обратно связанный список
Это распространенный вопрос, с которым разработчики могут столкнуться при подготовке к интервью.
Вопрос: Учитывая односвязный список (заголовок), переверните список и верните обратный список.
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Input: head = [1,2] Output: [2,1] Input: head = [] Output: []
Подход с реверсированием на месте. Этот метод включает в себя изменение следующих указателей каждого узла в списке, чтобы они указывали на предыдущий узел, эффективно изменяя направление списка.
function reverseLinkedList(head) {
let previous = null;
let current = head;
while (current) {
let next = current.next; // Save the next node
current.next = previous; // Reverse the current node's pointer
previous = current; // Move the previous node to the current node
current = next; // Move to the next node
}
return previous; // the head of the reversed list is the previous node
}
Объяснение.Рассмотрите следующий связанный список:
A -> B -> C -> D -> E
Метод реверсирования на месте работает путем итерации по списку и реверсирования следующего указателя каждого узла, чтобы он указывал на предыдущий узел.
Initial State current = A previous = null A -> B -> C -> D -> E First Iteration current = B previous = A A <- B -> C -> D -> E Second Iteration current = C previous = B A <- B <- C -> D -> E Third Iteration current = D previous = C A <- B <- C <- D -> E Forth Iteration current = E previous = D A <- B <- C <- D <- E Last Iteration current = null previous = E A <- B <- C <- D <- E
Этот метод изменяет направление указателей в связанном списке, делая первый элемент последним, а последний элемент — первым путем итерации по списку. Он имеет временную сложность O(n) и пространственную сложность O(1).
Массивный подход. Вы также можетепреобразовать связанный список в массив, перевернуть массив, а затем перестроить связанный список, используя обращенный массив.
function reverseLinkedList(head) {
let current = head;
let arr = [];
while (current) {
arr.push(current);
current = current.next;
}
arr.reverse();
for (let i = 0; i < arr.length - 1; i++) {
arr[i].next = arr[i + 1];
}
arr[arr.length - 1].next = null;
return arr[0];
}
В этом подходе есть компромисс с точки зрения пространственной сложности, которая составляет O (n), что может быть проблемой, если связанный список обширен. Временная сложность O(n).
Рекурсивный подход. Он работает следующим образом: порядок элементов в меньших частях списка меняется на противоположный, а затем в текущий элемент вносятся изменения, чтобы он указывал на предыдущий элемент.
function reverseLinkedList(current, previous = null) {
if (current == null) {
return previous;
}
let next = current.next;
current.next = previous;
return reverseLinkedList(next, current);
}
Как и метод массива, он также имеет пространственную сложность O(n) и временную сложность O(n). Объемная сложность этого подхода составляет O(n), потому что для каждого рекурсивного вызова в стек вызовов добавляется новый вызов функции, и эти вызовы функций занимают определенный объем памяти. Поскольку в списке n узлов, максимальная глубина стека вызовов будет равна n.
19. Удалить N-й узел из конца списка
Вопрос. Учитывая head связанного списка, удалите узел nth из конца списка и верните его заголовок.
Подход с использованием длины: во-первых, мы можем найти длину связанного списка, а затем использовать эту информацию, чтобы определить, какой узел удалить.
function removeNthFromEnd(head, n) {
let length = 0;
let current = head;
// Find the length of the linked list
while (current) {
length++;
current = current.next;
}
// Find the node to remove
current = head;
let previous = null;
for (let i = 0; i < length - n; i++) {
//the index of the node (length-n)
previous = current;
current = current.next;
}
// remove the nth node from the end
if(previous) previous.next = current.next;
else head = head.next;
return head;
}
Этот код сначала использует цикл while, чтобы найти длину связанного списка. Затем он использует еще один цикл для повторного обхода списка, на этот раз останавливаясь на n-м узле с конца, где он обновляет следующий указатель предыдущего узла, чтобы пропустить текущий узел, эффективно удаляя его из списка.
Этот подход имеет временную сложность O (n) и пространственную сложность O (1), и его легче понять.
Подход со скользящим окном. Этот подход похож на подход с двумя указателями, но использует окно размера n для отслеживания n-го узла с конца списка.
Первый узел в окне — это n-й узел с конца списка, а второй узел — голова списка. В коде используются два указателя, которые изначально установлены на фиктивный узел.
function removeNthFromEnd(head, n) {
let dummy = new ListNode(0);
dummy.next = head;
let first = dummy;
let second = dummy;
// Iterate first pointer n steps ahead
for (let i = 0; i < n; i++) {
first = first.next;
}
// Iterate both pointers until the first pointer reaches to the end
while (first.next != null) {
first = first.next;
second = second.next;
}
// remove the nth node from the end
second.next = second.next.next;
//return the new head
return dummy.next;
}
Узел-пустышка добавляется в начало списка для обработки случая, когда заголовок списка удаляется. Первый указатель помещается в n-й узел с конца, который является началом окна в начале. После этого оба указателя перемещаются вместе, пока первый не достигнет конца списка. Второй указатель будет ссылаться на конец окна (узел, предшествующий n-му узлу с конца).
Этот подход имеет временную сложность O(n), потому что нам нужно выполнить итерацию по списку один раз, а пространственная сложность равна O(1).
160. Пересечение двух связанных списков
Вопрос: Имея заголовки двух односвязных списков headA и headB, вернуть узел, в котором эти два списка пересекаются. Если пересечения нет, вернуть null.
Вывод: пересечение в точке ‘c1’.
Подход:мы можем использоватьдва указателя, чтобы отслеживать изменения узла.
Предположим, у нас есть два указателя, которые изначально установлены на заголовки двух связанных списков.
function getIntersectionNode(headA, headB) {
let p1 = headA, p2 = headB;
while (p1 !== p2) {
p1 = p1 ? p1.next : headB;
p2 = p2 ? p2.next : headA;
}
return p1;
}
Цикл while выполняется до тех пор, пока p1 и p2 не равны. Если они идентичны, они достигли узла пересечения, и функция возвращает узел.
На каждой итерации цикла while, если p1 не равен нулю, он устанавливается на следующий узел в списке. В противном случае это означает, что он достиг конца первого списка, поэтому он устанавливается в начало второго списка (headB). Этот код используется для обеспечения того, чтобы оба указателя проходили одинаковое количество узлов. Когда один указатель достигает конца своего списка, ему присваивается начало другого списка, чтобы он мог продолжить обход.
21. Объединить два отсортированных списка
Вопрос. Вам даны заголовки двух отсортированных связанных списков head1 и head2. Объедините два списка в один отсортированный список. Возвращает заголовок объединенного связанного списка.
Подход. Для этого вопроса может быть проще использовать рекурсивную функцию.
var mergeTwoLists = function(head1, head2) {
if (!head1) {
return head2;
} else if (!head2) {
return head1;
}
if(head1.val < head2.val) {
head1.next = mergeTwoLists(head1.next, head2);
return head1;
} else {
head2.next = mergeTwoLists(head1, head2.next);
return head2;
}
};
Если в одном из двух списков нет элементов, мы должны вернуть отсортированный список, не равный нулю. Это базовый случай для рекурсии.
Если ни одна из головок не равна нулю, мы сравним их значения. Если значение head1 меньше, чем head2, следующий узел head1 является результатом слияния следующего узла обоих списков. Затем он возвращает head1. Эта логика работает для обоих списков.
Этот рекурсивный подход продолжается до тех пор, пока не будет достигнут конец обоих списков, и конечным результатом будет полностью объединенный и отсортированный связанный список.
Временная сложность этого решения — O(n log(n)), n — общее количество узлов, а пространственная сложность — O(log(n)).
141. Цикл связанного списка
Вопрос.По заданному заголовку связанного списка определите, есть ли в нем цикл.
Подход с двумя указателями: у нас могут быть два указателя, которые проверяют один и два шага вперед по списку. Если два указателя когда-либо указывают на один и тот же узел, это означает, что в списке есть цикл.
function hasCycle(head) {
let first = head;
let second = head;
while (second && second.next) {
first = first.next;
second = second.next.next;
if (first === second) {
return true;
}
}
return false;
}
Временная сложность этого алгоритма равна O(n), где n — количество узлов в связанном списке. Сложность пространства равна O(1), потому что она постоянна и не растет с входными данными.
Подход с набором: этот метод состоит в отслеживании посещенных узлов как перемещений. Если мы можем обнаружить, что посещали узел раньше, мы можем сказать, что существует цикл.
function hasCycle(head) {
let set = new Set();
let current = head;
while (current) {
if (set.has(current)) {
return true;
}
set.add(current);
current = current.next;
}
return false;
}
Если текущий узел уже есть в наборе, значит, в списке есть цикл. Если текущего узла нет в наборе, добавьте его в набор и перейдите к следующему узлу. Если мы находимся в конце списка без цикла, возвращаем false.
Этот подход также имеет временную сложность O(n), но пространственную сложность составляет O(n), поскольку он использует набор для хранения посещенных узлов. В зависимости от ограничений (содержащих списки меньшего размера) могут быть приемлемы оба подхода.
Заключение
Можно сказать, что нет окончательного решения любой проблемы. Будут разные подходы, которые приходят на ум. Пока вы знаете об ограничениях, компромиссах между методами и о том, как можно улучшить ваше решение, у вас все отлично!
