Обращение связанного списка — очень простой, но очень популярный алгоритмический вопрос на собеседовании. Он также появился в 24-м вопросе «Предложения меча». Насколько он популярен, вы можете увидеть в списке ниже.
По данным Niuke.com,Вопросы интервью с перевернутым связанным списком занимают двойные списки [Проверено на прошлой неделе] и [Любимый тест по исследованиям и разработкам] соответственно., Все известные интернет-компании, такие как NetEase и Byte, прошли тест, но показатель успешности составляет всего 30%, поэтому в этой статье мы изучим два метода реализации для реверсирования связанных списков.
Данные таблицы лидеров:www.nowcoder.com/activity/oj
тема
Название: Sword to Offer 24. Обратно связанный список
Описание: определите функцию, которая принимает в качестве входных данных головной узел связанного списка, переворачивает связанный список и выводит головной узел обращенного связанного списка.
Пример:
Ввод: 1->2->3->4->5->NULL
Вывод: 5->4->3->2->1->NULL
Ссылка на LeetCode:Ли ТШО's-talent.com/problems/post…
Реализация 1: стек
Все в стеке:Поскольку стек представляет собой структуру данных «первым пришел — последним вышел», процесс его выполнения показан на следующем рисунке:
Окончательный результат выполнения показан на следующем рисунке:
Код реализации выглядит следующим образом:
public ListNode reverseList(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
stack.push(head); // 存入第一个节点
while (head.next != null) {
stack.push(head.next); // 存入其他节点
head = head.next; // 指针移动的下一位
}
// 反转链表
ListNode listNode = stack.pop(); // 反转第一个元素
ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
while (!stack.isEmpty()) {
ListNode item = stack.pop(); // 当前节点
lastNode.next = item;
lastNode = item;
}
lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
return listNode;
}
Результат проверки LeetCode показан на следующем рисунке:
Реализация 2: Рекурсия
Код реализации выглядит следующим образом:
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
// 从下一个节点开始递归
ListNode reverse = reverseList(head.next);
head.next.next = head; // 设置下一个节点的 next 为当前节点
head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
return reverse;
}
Результат проверки LeetCode показан на следующем рисунке:
Суммировать
В данной работе мы использовалиStackА рекурсивный метод реализует функцию инверсии связанного списка, гдеStackМетод реализации заключается в использовании функции стека "последним пришел - первым вышел" для прямого обращения связанного списка.Идея реализации и код реализации относительно просты, но не очень идеальны с точки зрения производительности и потребления памяти, и может быть использован в качестве гарантированного плана реализации для написанного теста; рекурсивный метод имеет хорошие показатели с точки зрения производительности и потребления памяти, а также его код реализации очень лаконичен, читателю нужно только понять идею реализация кода.
Подпишитесь на официальный аккаунт «Java Chinese Community», чтобы отправить «Интервью», чтобы получать последние материалы интервью.