Эта серия представляет собой краткое изложение структур данных и алгоритмов, когда я искал работу много лет назад. Здесь есть базовые части и классические вопросы для интервью от крупных компаний. Впервые опубликовано на CSDN. Теперь он организован в серию для справки друзей, которым это нужно.Если есть какая-либо ошибка, пожалуйста, поправьте меня. Полный кодовый адрес этой серии находится по адресуздесь.
0 Обзор
В качестве базовой структуры данных во многих местах используется связанный список. Например, он используется в коде ядра Linux, исходном коде Redis и исходном коде Python. В дополнение к односвязным спискам существуют также двусвязные списки.Эта статья в основном посвящена односвязным спискам (включая некоторые темы циклических связанных списков, которые будут указаны в заголовке, а в других случаях это просто односвязные списки). Двусвязный список имеет хорошую реализацию в Redis, и я также скопировал копию на свой склад для тестирования.Соответствующий код этой статьи находится вздесь.
1 Определение
Сначала определите структуру односвязного списка, как показано ниже, определите две структуры узла связанного списка и связанного списка. Здесь я не определяю структуру связанного списка для сохранения такой информации, как указатель начала, указатель хвоста, длина связанного списка и т. д. Цель состоит в том, чтобы больше попрактиковаться в работе указателя.
// aslist.h
// 链表结点定义
typedef struct ListNode {
struct ListNode *next;
int value;
} listNode;
2 Основные операции
Основываясь на определении связанного списка в предыдущем разделе, мы выполняем несколько основных операций, включая инициализацию связанного списка, добавление узлов в связанный список и удаление узлов из связанного списка.
/**
* 创建链表结点
*/
ListNode *listNewNode(int value)
{
ListNode *node;
if (!(node = malloc(sizeof(ListNode))))
return NULL;
node->value = value;
node->next = NULL;
return node;
}
/**
* 头插法插入结点。
*/
ListNode *listAddNodeHead(ListNode *head, int value)
{
ListNode *node;
if (!(node = listNewNode(value)))
return NULL;
if (head)
node->next = head;
head = node;
return head;
}
/**
* 尾插法插入值为value的结点。
*/
ListNode *listAddNodeTail(ListNode *head, int value)
{
ListNode *node;
if (!(node = listNewNode(value)))
return NULL;
return listAddNodeTailWithNode(head, node);
}
/**
* 尾插法插入结点。
*/
ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node)
{
if (!head) {
head = node;
} else {
ListNode *current = head;
while (current->next) {
current = current->next;
}
current->next = node;
}
return head;
}
/**
* 从链表删除值为value的结点。
*/
ListNode *listDelNode(ListNode *head, int value)
{
ListNode *current=head, *prev=NULL;
while (current) {
if (current->value == value) {
if (current == head)
head = head->next;
if (prev)
prev->next = current->next;
free(current);
break;
}
prev = current;
current = current->next;
}
return head;
}
/**
* 链表遍历。
*/
void listTraverse(ListNode *head)
{
ListNode *current = head;
while (current) {
printf("%d", current->value);
printf("->");
current = current->next;
if (current == head) // 处理首尾循环链表情况
break;
}
printf("NULL\n");
}
/**
* 使用数组初始化一个链表，共len个元素。
*/
ListNode *listCreate(int a[], int len)
{
ListNode *head = NULL;
int i;
for (i = 0; i < len; i++) {
if (!(head = listAddNodeTail(head, a[i])))
return NULL;
}
return head;
}
/**
* 链表长度函数
*/
int listLength(ListNode *head)
{
int len = 0;
while (head) {
len++;
head = head->next;
}
return len;
}
3 вопроса интервью, связанные со связанным списком
3.1 Обратный порядок связанного списка
вопрос:Дан односвязный список1->2->3->NULL, в обратном порядке становится3->2->1->NULL.
развязать:Обычно используется круговой метод для соединения каждого узла в обратном порядке, как показано ниже:
/**
* 链表逆序，非递归实现。
*/
ListNode *listReverse(ListNode *head)
{
ListNode *newHead = NULL, *current = head;
while (current) {
ListNode *next = current->next;
current->next = newHead;
newHead = current;
current = next;
}
return newHead;
}
Если это немного ослепительно, то приходите к рекурсивному решению, а именно:
/**
* 链表逆序，递归实现。
*/
ListNode *listReverseRecursive(ListNode *head)
{
if (!head || !head->next) {
return head;
}
ListNode *reversedHead = listReverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return reversedHead;
}
3.2 Репликация связанного списка
вопрос:Учитывая односвязный список, скопируйте и верните новый узел заголовка связанного списка.
развязать:Также может быть два решения, нерекурсивное и рекурсивное, а именно:
/**
* 链表复制-非递归
*/
ListNode *listCopy(ListNode *head)
{
ListNode *current = head, *newHead = NULL, *newTail = NULL;
while (current) {
ListNode *node = listNewNode(current->value);
if (!newHead) { // 第一个结点
newHead = newTail = node;
} else {
newTail->next = node;
newTail = node;
}
current = current->next;
}
return newHead;
}
/**
* 链表复制-递归
*/
ListNode *listCopyRecursive(ListNode *head)
{
if (!head)
return NULL;
ListNode *newHead = listNewNode(head->value);
newHead->next = listCopyRecursive(head->next);
return newHead;
}
3.3 Объединение связанных списков
вопрос:Известны два упорядоченных односвязных списка, объедините два связанных списка, чтобы объединенный связанный список все еще был в порядке (Примечание: эти два связанных списка не имеют общего узла, то есть они не пересекаются). Если связанный список 11->3->4->NULL, связанный список 22->5->6->7->8->NULL, то объединенный связанный список будет1->2->3->4->5->6->7->8->NULL.
развязать:Это очень похоже на последний шаг сортировки слиянием — объединение двух упорядоченных связанных списков. Используйте 2 указателя для обхода двух связанных списков соответственно и объедините узел с меньшим значением в связанный список результатов. Если после завершения слияния одного связанного списка все еще есть узлы в другом связанном списке, добавьте оставшуюся часть другого связанного списка в конец полученного связанного списка. Код выглядит следующим образом:
/**
* 链表合并-非递归
*/
ListNode *listMerge(ListNode *list1, ListNode *list2)
{
ListNode dummy; // 使用空结点保存合并链表
ListNode *tail = &dummy;
if (!list1)
return list2;
if (!list2)
return list1;
while (list1 && list2) {
if (list1->value <= list2->value) {
tail->next = list1;
tail = list1;
list1 = list1->next;
} else {
tail->next = list2;
tail = list2;
list2 = list2->next;
}
}
if (list1) {
tail->next = list1;
} else if (list2) {
tail->next = list2;
}
return dummy.next;
}
Конечно, рекурсивную реализовать несложно, код такой:
ListNode *listMergeRecursive(ListNode *list1, ListNode *list2)
{
ListNode *result = NULL;
if (!list1)
return list2;
if (!list2)
return list1;
if (list1->value <= list2->value) {
result = list1;
result->next = listMergeRecursive(list1->next, list2);
} else {
result = list2;
result->next = listMergeRecursive(list1, list2->next);
}
return result;
}
3.4 Решение о пересечении связанных списков
вопрос:Имея два односвязных списка list1 и list2, определите, пересекаются ли эти два связанных списка. Если они пересекаются, найти узел пересечения.
Решение 1:Вы можете просмотреть list1 напрямую, а затем определить, находится ли каждый узел list1 в list2 по очереди, но сложность этого решенияO(length(list1) * length(list2)). Конечно, когда мы проходим по списку 1, мы можем использовать хэш-таблицу для хранения узлов списка 1, поэтому мы можем судить, снова проходя по списку 2. Временная сложность равнаO(length(list1) + length(list2)), пространственная сложностьO(length(list1)), так что пересекающиеся узлы находятся естественным образом. Конечно, есть лучшие способы найти пересечения.
Решение 2:Если два связанных списка пересекаются, то они должны быть одним и тем же узлом из пересечения. Предположим, что list1 имеет длину len1, list2 имеет длину len2 иlen1 > len2, то нам нужно только сначала пройти list1len1-len2Узел, затем два соединения проходят вместе, если вы встречаете равный узел, узел является первым пересечением.
/**
* 链表相交判断，如果相交返回相交的结点，否则返回NULL。
*/
ListNode *listIntersect(ListNode *list1, ListNode *list2)
{
int len1 = listLength(list1);
int len2 = listLength(list2);
int delta = abs(len1 - len2);
ListNode *longList = list1, *shortList = list2;
if (len1 < len2) {
longList = list2;
shortList = list1;
}
int i;
for (i = 0; i < delta; i++) {
longList = longList->next;
}
while (longList && shortList) {
if (longList == shortList)
return longList;
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
3.5 Определить, есть ли цикл в связанном списке
вопрос:Учитывая связанный список, определите, есть ли цикл в связанном списке.
Решение 1:Самый простой способ — использовать хеш-таблицу для записи появившихся узлов и обхода связанного списка.Если узел появляется повторно, это означает, что в связанном списке есть кольцо. Если вам не нужна хеш-таблица, вы также можете использовать узел связанного спискаListNodeПосещенное поле добавляется в структуру как метка, а посещенная метка равна 1, что также можно обнаружить. Поскольку мы еще не реализовали хэш-таблицу, код этого метода будет добавлен позже.
Решение 2:Лучший способАлгоритм цикла Флойда, алгоритм был впервые представлен罗伯特.弗洛伊德изобретение. Используя два указателя, быстрый и медленный, для перемещения по связанному списку, быстрый указатель делает два шага каждый раз, а медленный указатель делает каждый раз один шаг.Если быстрый и медленный встречаются, это означает, что есть кольцо, в противном случае нет звенеть. (Обратите внимание, что если связанный список имеет только один узел и не имеет цикла, он не войдет в цикл while)
/**
* 检测链表是否有环-Flod判圈算法
* 若存在环，返回相遇结点，否则返回NULL
*/
ListNode *listDetectLoop(ListNode *head)
{
ListNode *slow, *fast;
slow = fast = head;
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
printf("Found Loop\n");
return slow;
}
}
printf("No Loop\n");
return NULL;
}
void testListDetectLoop()
{
printf("\nTestListDetectLoop\n");
int a[] = {1, 2, 3, 4};
ListNode *head = listCreate(a, ALEN(a));
listDetectLoop(head);
// 构造一个环
head->next->next->next = head;
listDetectLoop(head);
}
Расширение:Если обнаружена петля, как найти точку входа в петлю связанного списка?
Во-первых, давайте докажем, почему алгоритм, упомянутый в Решении 2 выше, верен. Если в связанном списке нет кольца, поскольку быстрый указатель делает 2 шага за раз, он неизбежно достигнет конца связанного списка раньше медленного указателя и не встретится.
Если существует кольцо, если предположить, что быстрый и медленный указатели встречаются после s циклов, то расстояние, пройденное быстрым указателем, равно 2s, а расстояние, пройденное медленным указателем, равно s. Предположим, что число узлов в кольце равно r, для выполнения должны быть выполнены следующие условия: соответствовать количеству разs = nr. То есть следующее столкновение после начальной точки требует циклаrВторосортный.
2s - s = nr => s = nr
Как показано на рисунке ниже, длина кольца r=4, тогда следующее столкновение с начальной точкой должно пройти через 4 цикла.
Итак, как найти точку входа в кольцо? Ранее было известно, что первое столкновение должно повторяться r раз, а расстояние, пройденное медленным указателем при столкновении, равно s = r. Пусть общая длина связанного списка равна L, расстояние от головы связанного списка до входа в кольцо равно a, а расстояние от входа в кольцо до точки встречи равно x, тогдаL = a + r, можно вывестиa = (L-x-a),вL-x-a- расстояние от точки встречи до точки входа в кольцо,То есть расстояние a от начала связанного списка до записи в кольце равно расстоянию от точки встречи до записи в кольце..
s = r = a + x => a + x = (L-a) => a = L-x-a
Следовательно, после принятия решения о том, что в связанном списке есть кольцо, обход начинается с точки встречи и головного узла соответственно, и каждый раз два указателя делают один шаг.Когда два указателя равны, это точка входа кольцо.
/**
* 查找链表中环入口
*/
ListNode *findLoopNode(ListNode *head)
{
ListNode *meetNode = listDetectLoop(head);
if (!meetNode)
return NULL;
ListNode *headNode = head;
while (meetNode != headNode) {
meetNode = meetNode->next;
headNode = headNode->next;
}
return meetNode;
}
3.6 Связанный список имитирует сложение
вопрос:Для двух связанных списков значением узла каждого связанного списка является число в каждой цифре числа, попробуйте найти сумму чисел, представленных двумя связанными списками, и верните результат в виде связанного списка. Предполагая, что два связанных списка - это list1 и list2 соответственно, значения каждого узла list1 - это числа в единицах, десятках и сотнях числа 513 соответственно. Точно так же значения каждого узла list2 равны числа в цифрах числа 295. Сумма этих двух чисел равна 808, поэтому выходные данные выводятся в порядке от единиц до сотен, а возвращаемый список результатов выглядит следующим образом.
list1： (3 -> 1 -> 5 -> NULL)
list2： (5 -> 9 -> 2 -> NULL)
result： (8 -> 0 -> 8 -> NULL)
развязать:Эта тема более интересна и требует большего мастерства в операциях со связанными списками. Мы рассматриваем процесс сложения двух чисел и добавляем их последовательно от младшего к старшему.Если есть перенос, отмечаем флаг переноса до тех пор, пока старший бит не будет завершен. Пусть узел текущего бита является текущим, тогда имеются:
current->data = list1->data + list2->data + carry
(其中carry为低位的进位，如果有进位为1，否则为0)
Нерекурсивный код выглядит следующим образом:
/**
* 链表模拟加法-非递归解法
*/
ListNode *listEnumarateAdd(ListNode *list1, ListNode *list2)
{
int carry = 0;
ListNode *result = NULL;
while (list1 || list2 || carry) {
int value = carry;
if (list1) {
value += list1->value;
list1 = list1->next;
}
if (list2) {
value += list2->value;
list2 = list2->next;
}
result = listAddNodeTail(result, value % 10);
carry = ( value >= 10 ? 1: 0);
}
return result;
}
Нерекурсивная реализация выглядит следующим образом:
/**
* 链表模拟加法-递归解法
*/
ListNode *listEnumarateAddRecursive(ListNode *list1, ListNode *list2, int carry)
{
if (!list1 && !list2 && carry==0)
return NULL;
int value = carry;
if (list1)
value += list1->value;
if (list2)
value += list2->value;
ListNode *next1 = list1 ? list1->next : NULL;
ListNode *next2 = list2 ? list2->next : NULL;
ListNode *more = listEnumarateAddRecursive(next1, next2, (value >= 10 ? 1 : 0));
ListNode *result = listNewNode(carry);
result->value = value % 10;
result->next = more;
return result;
}
3.7 Вставка узла в упорядоченный одноциклический связанный список
вопрос:Зная упорядоченный односторонний круговой связанный список, вставьте узел и сохраните связанный список в порядке, как показано на следующем рисунке.
развязать:Прежде чем решать эту проблему, давайте рассмотрим упрощенную версию, которая заключается в том, чтобы вставить узел в упорядоченный односвязный список без петель и при этом обеспечить его порядок. Считается, что код для этой задачи знаком большинству людей, и его обычно рассматривают в двух случаях:
- 1) Если исходный связанный список пуст или вставленный узел имеет наименьшее значение, вставьте узел напрямую и установите его в качестве головного узла.
- 2) Если исходный связанный список не пуст, найдите первый узел, больший, чем значение узла, и вставьте его перед узлом. Если вставленный узел имеет наибольшее значение, он будет вставлен в конец.
Код реализации выглядит следующим образом:
/**
* 简化版-有序无循环链表插入结点
*/
ListNode *sortedListAddNode(ListNode *head, int value)
{
ListNode *node = listNewNode(value);
if (!head || head->value >= value) { //情况1
node->next = head;
head = node;
} else { //情况2
ListNode *current = head;
while (current->next != NULL && current->next->value < value)
current = current->next;
node->next = current->next;
current->next = node;
}
return head;
}
Конечно, эти два случая также можно обрабатывать вместе, используя вторичные указатели. следующее:
/**
* 简化版-有序无循环链表插入结点(两种情况一起处理)
*/
void sortedListAddNodeUnify(ListNode **head, int value)
{
ListNode *node = listNewNode(value);
ListNode **current = head;
while ((*current) && (*current)->value < value) {
current = &((*current)->next);
}
node->next = *current;
*current = node;
}
Далее рассмотрим ситуацию с круговым связанным списком, на самом деле необходимо учитывать следующие два момента:
- 1) предыдущее->значение ≤ значение ≤ текущее->значение: Вставить между предыдущим и текущим.
- 2) value – максимальное или минимальное значение: Вставьте его на стыке начала и конца и сбросьте значение головы, если оно минимальное.
код показывает, как показано ниже:
/**
* 有序循环链表插入结点
*/
ListNode *sortedLoopListAddNode(ListNode *head, int value)
{
ListNode *node = listNewNode(value);
ListNode *current = head, *prev = NULL;
do {
prev = current;
current = current->next;
if (value >= prev->value && value <= current->value)
break;
} while (current != head);
prev->next = node;
node->next = current;
if (current == head && value < current->value) // 判断是否要设置链表头
head = node;
return head;
}
3.8 Вывод K-го узла снизу связанного списка
вопрос:Дан простой односвязный список, выведите K-й узел из конца связанного списка.
Решение 1:Если это K-й узел в порядке, вы можете просто пройти его, не задумываясь. Новизна этой темы в том, что она заключается в выводе K-го узла снизу. Интуитивная идея состоит в том, что, если предположить, что длина связанного списка равна L, K-й узел снизу является узлом L-K+1 заказа. Если длина связанного списка равна 3, предпоследний узел является вторым узлом в порядке. Таким образом, необходимо дважды пройти по связному списку: один раз, чтобы найти длину, и один раз, чтобы найти узел.
/**
* 链表倒数第K个结点-遍历两次算法
*/
ListNode *getLastKthNodeTwice(ListNode *head, int k)
{
int len = listLength(head);
if (k > len)
return NULL;
ListNode *current = head;
int i;
for (i = 0; i < len-k; i++) //遍历链表，找出第N-K+1个结点
current = current->next;
return current;
}
Решение 2:Конечно, лучше пройти один раз и установить два указателя p1 и p2.Сначала оба p1 и p2 указывают на голову, а затем p2 перемещается вперед на k шагов, так что между p1 и p2 остается интервал из k узлов. Наконец, p1 и p2 перемещаются вперед одновременно, и когда p2 достигает конца связанного списка, p1 просто указывает на K-й узел снизу. код показывает, как показано ниже:
/**
* 链表倒数第K个结点-遍历一次算法
*/
ListNode *getLastKthNodeOnce(ListNode *head, int k)
{
ListNode *p1, *p2;
p1 = p2 = head;
for(; k > 0; k--) {
if (!p2) // 链表长度不够K
return NULL;
p2 = p2->next;
}
while (p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}