c++ - 使用双指针和递归的单链表反转

Question

我尝试使用指向头节点的指针来反转链表，该头节点在下面的函数中用作参数：

void reverseLLRec(Node** start) {
    Node* curr;
    // Empty list
    if (*start == NULL) {
        return;
    }
    curr = *start;
    if (curr->link == NULL) {
        *start = curr;
        return;
    }
    
    reverseLLRec(&(curr->link));
    curr->link->link = curr;
    curr->link = NULL;
}

我得到以下输出 -

似乎*start指针没有被修改为指向新的头。

我在这里做错了什么？

标签： c++recursiondata-structureslinked-list

Answer 1

因为您curr->link通过将其地址传递给递归调用来进行更改，所以下一次使用的curr->link不再引用您想要的节点。

你不应该让递归调用改变curr->link。另一方面，您应该更改*start，因为它必须指代新的头（反转后）。所以将该地址传递给递归调用。

所以替换这一行：

reverseLLRec(&(curr->link));

用这两行：

*start = curr->link;
reverseLLRec(start);