C ++ Reverse Linked List Рекурсивно Почему это работает?

Question

Это проблема: https://leetcode.com/problems/reverse-linked-list/

Я знаю решение (и оно копируется по всему Интернету), но я не понимаю как это работает ... Итак:

    struct ListNode{
        int data;
        ListNode* next;
    };

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

это работает.

Теперь я получаю его через отладчик и вижу вещи, которые я не понимаю ...

Предположим, мыу нас есть связанный список:

1->2->3->NULL

1) Мы передали последнюю 3->Null часть в ListNode* node = reverseList(head->next);, и теперь она return head; и теперь ListNode* node = 3->NULL;

Хорошо, node == 3->NULL и head == 2->3->NULL

2) Давайте перейдем к head->next->next = head:

Сейчас head == 2->3->2->3... НО ПОЧЕМУ node == 3->2->3->2... ???

Как они связаны?Я совершенно сбит с толку.

3) на следующей строке head -> next = NULL мы видим, что это снова влияет на head и node:

Как видите, я не понимаю связи между node и head.Поэтому я не понимаю, как это работает, и я чувствую, что не понимаю, как работают эти связанные списки в целом.Может быть, кто-то может мне помочь?Цени это.

Answer 1

К сожалению, у меня недостаточно репутации, чтобы оставлять комментарии, поэтому я собираюсь опубликовать ответ и надеюсь, что он вам поможет. Я собираюсь использовать картины для рисования, чтобы упростить визуализацию. Давайте начнем:

Допустим, у нас есть список 1-> 2-> 3->, поэтому он начинается так:

Теперь мы запускаем функцию, и она работает до тех пор, пока не доберется до первой рекурсии, где она начинается с новой головы, и у нас будет следующая ситуация:

Затем функция запускается снова, и мы получаем следующий результат:

Затем мы начинаем с нового заголовка (3), но здесь последняя функция возвращает заголовок, поскольку выполняется условие if head->next == NULL. Итак имеем:

Затем мы следуем функции до конца, изменяя head->next->next = head и head->next = NULL, поэтому имеем:

Затем функция возвращает узел, и мы возвращаемся к исходному вызову. Затем мы делаем те же шаги и получаем:

В конце функция возвращает узел, поэтому мы получаем:

Надеюсь, это поможет вам, и извините за низкое качество ответа, но мне легче решать рекурсию при его визуализации, а самый простой способ визуализации - рисовать.

Answer 2

Хорошо, возможно, я сам нашел ответ. опять проблема здесь:

        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node;

У меня был вопрос, почему строки 2 и 3, которые меняют head, также влияют (меняют) node?

это потому, что node является указателем, и он «указывает» на тот же адрес в памяти, что и head->next.

Вы действительно можете увидеть это на первом скриншоте:

0x100300020 является адресом node

0x100300020 является адресом head->next

они указывают на один и тот же адрес в памяти.

Итак, когда мы делаем:

        head -> next -> next = head;
        head -> next = NULL;

мы также изменяем его на «вещь, хранящуюся» по адресу, на который указывает node.