Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 30
Часть VIII. Вопросы собеседования
Структуры данных. Вопросы и советы
2. Связные списки
ОглавлениеВопросы про связные списки могут показаться трудными. Но есть и хорошие новости – таких вопросов немного, а множество задач являются всего лишь разновидностями типовых вопросов о связных списках.
Задачи на связные списки предполагают, что вы можете реализовать связный список с нуля.
Создание связного списка
Следующий код реализует очень простой односвязный список:
1 class Node {
2 Node next = null;
3 int data;
4
5 public Node(int d) {
6 data = d;
7 }
8
9 void appendToTail(int d) {
10 Node end = new Node(d);
11 Node n = this;
12 while (n.next!= null) {
13 n = n.next;
14 }
15 n.next = end;
16 }
17 }
Обратите внимание: когда вы говорите о связном списке на собеседовании, вы должны понимать, о каком списке – односвязном или двусвязном – идет речь.
Удаление узла из односвязного списка
Удаление узла из односвязного списка – достаточно простая задача. Дан узел n, нам нужно найти предыдущий узел prev и установить prev.next в n.net. Если у нас есть двусвязный список, нам нужно обновить n.next, чтобы установить n.next.prev в n.prev. Не забудьте сделать проверку на null-указатель и при необходимости обновить начало и конец списка.
Если вы реализуете код на C/С++ или другом языке, требующем контроля памяти, вам нужно освободить память, которую занимал удаляемый узел.
1 Node deleteNode(Node head, int d) {
2 Node n = head;
3
4 if (n.data == d) {
5 return head.next; /* перемещаем голову */
6 }
7
8 while (n.next!= null) {
9 if (n.next.data == d) {
10 n.next = n.next.next;
11 return head; /* голова списка не изменяется */
12 }
13 n = n.next;
14 }
15 return head;
16 }
Метод бегунка
Метод бегунка (или второго указателя) используется во многих задачах по связным спискам. Вы «пробегаетесь» по связному списку двумя указателями одновременно.
При этом один указатель называется «быстрым», а другой – «медленным».
Лучше всего продемонстрировать этот метод на примере. Существует связный список a1->a2->…->an->b1->b2->…->bn и его необходимо преобразовать в вид: a1->b1->a2->b2->… ->an->bn. Вы не знаете длину связного списка, но вы точно знаете, что длина – четное число.
У вас есть два указателя – p1 (быстрый) и p2 (медленный). За одну итерацию p1 перемещается на два элемента, а p2 – на один. Когда p1 достигнет конца, p2 будет находиться в середине списка. Переместив p1 обратно (в начало списка), можно провести реорганизацию. На каждой итерации p2 выбирает элемент и вставляет его после p1.
Рекурсия и связные списки
Много задач о связных списка решаются с помощью рекурсии. Получив задание, вы должны проверить, можно ли использовать рекурсивный подход. Сейчас мы не будем подробно говорить о рекурсии, этой теме будет посвящен отдельный раздел.
Вы должны помнить, что рекурсивные алгоритмы занимают как минимум O(n) пространства, где n – глубина рекурсии. Все рекурсивные алгоритмы можно заменить на итерационные, но более сложные алгоритмы.
Вопросы собеседования
2.1. Напишите код, удаляющий дубликаты из несортированного связного списка.
Дополнительно
Как вы будете решать задачу, если запрещается использовать временный буфер?
2.2. Реализуйте алгоритм для поиска в односвязном списке k-го элемента с конца.
2.3. Реализуйте алгоритм, удаляющий узел из середины односвязного списка (доступ дан только к этому узлу).
Пример
Ввод: узел c из списка a->b->c->d->e
Вывод: ничего не возвращается, но новый список имеет вид: a->b->d->e
2.4. Напишите код, разбивающий связный список вокруг значения x, так чтобы все узлы, меньшие x, оказались перед узлами, большими или равными x.
2.5. Два числа хранятся в виде связных списков, в которых каждый узел содержит один разряд. Все цифры хранятся в обратном порядке, при этом первая цифра числа находится в начале списка. Напишите функцию, которая суммирует два числа и возвращает результат в виде связного списка.
Пример
Ввод: (7->1->6) + (5->9->2). Это означает 617 + 295.
Вывод: 2->1->9, что означает 912.
Дополнительно
Решите задачу, предполагая, что цифры записаны в прямом порядке.
Ввод: (6 – > 1 – > 7)+ (2 – > 9 – > 5). Это означает 617 + 295.
Вывод: 9 – > 1 – > 2, что означает 912.
2.6. Для кольцевого связного списка реализуйте алгоритм, возвращающий начальный узел петли.
Определение
Кольцевой связный список – это связный список, в котором указатель последующего узла связан с более ранним узлом, образуя петлю.
Пример
Ввод: A->B->C->D->E->C (предыдущий узел C)
Вывод: C
2.7. Реализуйте функцию, проверяющую, является ли связный список палиндромом.
Дополнительные вопросы: деревья и графы (4.4), объектно-ориентированное проектирование (7.10), масштабируемость и лимиты памяти (11.7), модерирование (17.13).
