Несколько дней назад друг пошел брать интервью у ByteDance, и интервьюер задал ему вопроссвязанный списокСвязанная проблема с алгоритмом, но он некоторое время не решал ее, поэтому он пришел спросить меня, я чувствую, что это неплохая проблема, давайте поговорим об этом.
тема
На самом деле этодеформацияПроблема обращения связанного списка примерно описывается следующим образом
Учитывая заголовок головного узла односвязного списка, реализуйте функцию для настройки односвязного списка, чтобы каждый K узлов был группой обратного порядка,и начать с конца связанного списка, если оставшихся узлов в голове недостаточно для группы, обратный порядок не требуется. (Невозможно использовать очередь или стек в качестве вспомогательного)
Например: Связанный список: 1->2->3->4->5->6->7->8->null, K = 3. Тогда 6->7->8, 3->4->5, 1->2 составляют группу каждого. После настройки: 1->2->5->4->3->8->7->6->нуль. Среди них 1 и 2 не корректируются, потому что не хватает группы.
отвечать
Сложность этого вопроса в том, что он начинается с конца связанного списка, а не с конца связанного списка.голова, если это голова, то нам это сделать проще, потому что можно пройти по связному списку и разбить его на группу, чтобы каждый раз при обходе k менять порядок. Но он отличается от конца, потому что это односвязный список, вы не можете просмотреть группу в обратном направлении. Однако в этом вопросе определенно лучше использовать рекурсию.Для предложений по рекурсии см. Статью, которую я написал ранее.Почему вы не можете изучить рекурсию? Попрощайтесь с рекурсией и расскажите о своем опыте., в этой статье написано несколько подпрограмм о рекурсии.
Сделайте аналогичный разворот
Прежде чем ответить на этот вопрос, давайте посмотримЕсли начать с головы,Что я должен делать? Например: связанный список: 1->2->3->4->5->6->7->8->null, K = 3. После настройки: 3->2->1->6->5->4->7->8->нуль. Среди них 7 и 8 не корректируются, т.к. не хватает для одной группы.
По этому вопросу, если вы не знаете, как перевернуть односвязный список, вы можете прочитать то, что я написал раньшеКак элегантно перевернуть односвязный список
Мы можем решить эту задачу с помощью рекурсии, предполагая, что функция метода reverseKNode() состоит в том, чтобы изменить порядок между каждыми K узлами односвязного списка (отголоваФункция метода reverse() состоит в том, чтобы перевернуть односвязный список.
Затем для этого односвязного списка ниже, где K = 3.
Опять же, если вы не понимаете эту рекурсию, я предлагаю вам прочитать мою рекурсивную статью
Затем нам просто нужно соединить две части вместе. Окончательный результат выглядит следующим образом:
код показывает, как показано ниже:
//k个为一组逆序
public ListNode reverseKGroup(ListNode head, int k) {
ListNode temp = head;
for (int i = 1; i < k && temp != null; i++) {
temp = temp.next;
}
//判断节点的数量是否能够凑成一组
if(temp == null)
return head;
ListNode t2 = temp.next;
temp.next = null;
//把当前的组进行逆序
ListNode newHead = reverseList(head);
//把之后的节点进行分组逆序
ListNode newTemp = reverseKGroup(t2, k);
// 把两部分连接起来
head.next = newTemp;
return newHead;
}
//逆序单链表
private static ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode result = reverseList(head.next);
head.next.next = head;
head.next = null;
return result;
}
вернуться к этой теме
Можно сказать, что эти два вопроса очень похожи, за исключением того, что один начинается с головы, а этот начинается с головы, что также является 25-м вопросом leetcode. Во время интервью часто проводятся деформации, такие как этот вопрос с перебором байтов, который меняется отхвостикКогда вы начинаете настраивать, вы можете некоторое время не знать, как это сделать. Конечно, кто-то может сразу среагировать и убить его за секунды.
На самом деле, эту задачу очень легко решить, вам нужно сделать это только один раз в односвязном списке.обратный порядок, который может быть преобразован вСобрать из головы, а потом по моему решению выше, после обработки поставить результатснова обратный порядокВот и все. Два разворота эквивалентны отсутствию разворотов.
Например, для связанного списка (где K = 3)
1. Сначала в обратном порядке
2. Результат после обработки следующий
3. Потом поставить результатобратный порядокОдин раз результат такой
код показывает, как показано ниже
public ListNode solve(ListNode head, int k) {
// 调用逆序函数
head = reverse(head);
// 调用每 k 个为一组的逆序函数（从头部开始组起）
head = reverseKGroup(head, k);
// 在逆序一次
head = reverse(head);
return head;
}
Подобно тому, как в этом случае необходимо сначала обратить вспять, два связанных списка должны быть добавлены вместе.Этот вопрос также был написан для вопросов с перебором байтов.Второй вопрос на рисунке ниже
Эта проблема требует сначала изменить порядок двух связанных списков, затем добавить узлы и, наконец, объединить их.
Суммировать
Что касается вопросов по алгоритму связанного списка, я слышал, что это довольно распространено во время интервью. Вы можете уделить ему больше внимания. Если вы столкнетесь с хорошим вопросом по алгоритму связанного списка, вы можете бросить его мне.
Есть урожай? Я надеюсь, что старые айроны придут к комбо из трех ударов и покажут больше людей, чтобы увидеть эту статью.
1,поставь мне лайк, вы можете позволить большему количеству людей увидеть эту статью и, кстати, вдохновить меня, хи-хи.
2. Старые утюги, обратите на меня вниманиеоригинальныйПубличный аккаунт WeChat «Handsome Play Programming**», посвященный написаниюалгоритм + основы компьютера(компьютерная сеть + операционная система + база данных + Linux). Сохраните это, чтобы вы могли получить что-то после прочтения, если вы мне не верите, ударьте меня.
Напоследок хотелось бы порекомендовать вам давно собранный гитхаб, на этом гитхабе собраны сотни часто используемых электронных книг, а также указан адрес для скачивания., некоторые скриншоты выглядят следующим образом