Что-то не так при рекурсивном изменении связанного списка
Я пытаюсь решить задачу кода, которая требует отменить связанный список. Дан указатель на головной узел.
Вот моя попытка:
struct ListNode* reverseList(struct ListNode* head) {
if (head==NULL || head->next==NULL) return head;
struct ListNode* p=reverseList(head->next);
p->next=head;
return head;
}
Когда я запускаю всухую, кажется, все работает нормально. Но когда я отправляю код для тестирования, возникает ошибка превышения срока (TLE).
Почему это происходит? Что я делаю не так?
Очевидно, что если вы собираетесь в какой-то момент перевернуть список, вам нужно установить для head->next значение null, поскольку теперь это будет последний элемент в перевернутом списке. Ваш код этого не делает.
проверка имеет смысл, рекурсивный вызов тоже. но строки после неверны. Я рекомендую запустить его на простом примере с тремя узлами и работать над ним построчно (ровно рисуя кадры стека), чтобы попытаться найти проблему.
Обучение программированию на пути, состоящем из шагов, которые одинаково хорошо работают для C и C++, является узким и запутанным. Позже будет полезно и нетривиально узнать различия. Но сейчас лучше выбрать один из двух языков, и выучить его будет гораздо проще.
Предполагаете ли вы использовать рекурсивную функцию? В противном случае TLE можно было бы объяснить гораздо более быстрым циклом по списку и ожидаемым решением.
Вы используете C или C++? Вам следует использовать оба тега только в том случае, если речь идет о чем-то вроде сравнения между ними. В противном случае укажите тег конкретного языка, который вы используете.
Ответы 1
С вашей обратной функцией есть две отдельные проблемы:
Он введет цикл в связанный список, если он имеет более одного узла. Это означает, что если есть код, который не ожидает цикла, а просто наивно перебирает все узлы результирующего списка, он попадет в бесконечный цикл. Это может объяснить полученную вами ошибку ограничения времени.
Он возвращает исходный заголовок списка. Вместо этого он должен вернуть хвост исходного списка, поскольку это будет первый узел перевернутого списка.
Давайте возьмем простой пример связанного списка всего с двумя узлами со значениями 1 и два. Затем, когда вызывается reverseList, мы можем визуализировать состояние следующим образом:
head
↓
┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │
│ next: ──────────►│ next: NULL │
└────────────┘ └────────────┘
Затем у нас есть рекурсивный вызов, в котором в качестве аргумента передается ссылка на второй узел. Внутри этого рекурсивного вызова этот указатель — head. Я назову это head' (с апострофом) здесь:
head head'
↓ ↓
┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │
│ next: ──────────►│ next: NULL │
└────────────┘ └────────────┘
Здесь мы используем базовый случай, и рекурсивный вызов возвращает ссылку на второй узел, которому в контексте вызова присвоена p:
head p
↓ ↓
┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │
│ next: ──────────►│ next: NULL │
└────────────┘ └────────────┘
Затем выполняется p->next=head и мы получаем:
head p
↓ ↓
┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │
┌─►│ next: ──────────►│ next: ─┐ │
│ └────────────┘ └────────│───┘
└──────────────────────────────┘
Цикл создан. И теперь, когда return head выполняется, мы видим, что возникают две проблемы: возвращается неверная ссылка на узел, и цикл не прерывается.
Следующий адаптированный код исправляет обе проблемы:
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL) return head;
struct ListNode* newHead = reverseList(head->next);
// The tail of the recursively reversed list is at head->next.
// Append the current node (head) at that tail
head->next->next = head;
// And terminate the list at the new tail:
head->next = NULL;
// Return the new head, not the old head
return newHead;
}
p->next=head;вообще не имеет смысла.p— это перевернутый список (исключая заголовок), и вы хотите установить следующий элемент этого списка в заголовок?