Условие задачи: дан связный список (linked list), поменять порядок элементов на противоположный.
Примеры: Вход: 1->2->3->4->5, Выход: 5->4->3->2->1 Вход: 1, Выход: 1
Решение :
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null; // предыдущий узел ListNode curr = head; // текущий узел while(curr != null) { // пока не достигнем конца списка ListNode nextTemp = curr.next; // сохраняем ссылку на следующий узел curr.next = prev; // меняем ссылку у текущего узла на предыдущий узел prev = curr; // перемещаем указатель на предыдущий узел на текущий узел curr = nextTemp; // перемещаем указатель на текущий узел на следующий узел }
return prev; // возвращаем новую голову списка (бывший последний элемент) }
}
Идея алгоритма заключается в итеративном переборе элементов связного списка с помощью указателей. В начале мы устанавливаем указатель на предыдущий узел равным null, а указатель на текущий узел равным голове списка. Затем мы перебираем каждый узел, меняем ссылку на следующий узел на ссылку на предыдущий узел, перемещаем указатель на предыдущий узел на текущий узел и перемещаем указатель на текущий узел на следующий узел. Когда мы доходим до конца списка, возвращаем новую голову списка (бывший последний элемент).
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov