为什么这段反转链表的代码不起作用?我想确切地知道我做错了什么。
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。
您的反向函数有两个明显的问题:
当链表有多个节点时,就会引入环。这意味着,如果有代码不期望循环,而只是天真地迭代结果列表的所有节点,那么它将进入无限循环。这可以解释您收到的时间限制错误。
它返回列表的原始头部。相反,它应该返回原始列表的tail,因为这将是反转列表的第一个节点。
让我们举一个简单的例子,链表只有两个节点,值为 1 和 2。然后当调用
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;
}