Давайте объясним функцию reverseList, которая переворачивает односвязный список, шаг за шагом:

(следуйте процессу повторения кода-статьи-кода, чтобы лучше понять)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* restOfList = reverseList(head->next);
 //1. base case/ last return storing teqnique
        // 2. using recursive process reversly / when returning

        // Reverse the pointers
        head->next->next = head; // 3 no node
        head->next = nullptr; // we are deleting the current head next, because we will put the node before that
        //in its next on next recursive call

        return restOfList; 
        // we return this, because it will always returnt he last ending value, which is the
        // base case return value and we need the last head.
    }
  1. Базовый случай: первое, что проверяет функция, это то, является ли head либо nullptr, либо он не имеет узла next (head->next равен nullptr). Если одно из этих условий истинно, это означает, что связанный список имеет только один узел или пуст. В таких случаях реверсировать нечего, поэтому функция напрямую возвращает узел head.
  2. Рекурсивный реверс: если head не nullptr и в связанном списке имеется более одного узла, функция переходит в рекурсивную часть.
  • Он вызывает reverseList(head->next) рекурсивно, передавая узел next текущего head. Этот рекурсивный вызов эффективно переворачивает остальную часть связанного списка, начиная с узла после текущего head.
  • Рекурсивные вызовы продолжаются до тех пор, пока мы не достигнем последнего узла в исходном связанном списке.

3. Обратные указатели: после достижения базового случая функция начинает выполнение обратного процесса.

  • Когда функция начинает возвращаться из базового случая (т.е. рекурсивные вызовы начинают раскручиваться), она достигает строк:

голова-›следующая-›следующая = голова;

head-›next = nullptr;

Эти две строки меняют направление указателей в связанном списке. Они заставляют указатель next узла после head указывать обратно на head, эффективно изменяя порядок узлов. В этот момент текущий head становится новым концом списка.

4. Вернуть новую головку:

Наконец, функция возвращает restOfList, который является заголовком недавно перевернутого связанного списка. Это последний головной узел, который был исходным хвостовым узлом перед процессом реверсирования.

Он использует рекурсивный стек для изменения порядка узлов «снизу вверх». Процесс обращения связанного списка в первую очередь достигается за счет изменения указателей между узлами.