使用指针指针数组来操作它指向的指针（C++）

Question

我一直在做我自己的练习，以便在C++中变得更好（用我写的链表来搞乱）。我想要做的是通过扭转指针来颠倒列表，而不是仅仅将数据“反向打印”（这是相对直接的）。

我有一个指向指针的数组，每个指向链表中的一个节点。但这不是一个关于链表动态的问题（我知道），还有更多关于指针魔术师的问题。

一个node看起来是这样的，

template<class T> 
struct node { 
    T data; 
    node *next; 

    node(T value) : data(value), next(nullptr) {} 
}; 

，问题中的代码，

node<T> **reverseArr[listLength]; 
    node<T> *parser = root; 

    for (auto i : reverseArr) { 
     i = &parser; 
     parser = parser->next; 
    } 

    root = *(reverseArr[listLength - 1]); 
    for (int ppi = listLength - 1; ppi >= 0; --ppi) { 
     if (ppi == 0) { 
      (*reverseArr[ppi])->next = nullptr; 
      //std::cout << "ppi is zero!" << "\t"; 
     } 
     else { 
      (*reverseArr[ppi])->next = (*reverseArr[ppi - 1]); 
      //std::cout << "ppi, 'tis not zero!" << "\t"; 
     } 
    } 

我的逻辑：

• 新root是列表的最后一个元素，
• 遍历数组
• 将当前节点的next指针设置为前一个节点，方法是将当前节点的nextNode设置为循环中的下一个节点。

发生了什么事：

• 如果我离开的评论调试打印语句，什么都没有。函数的调用，但链表仍然保持不变（不反转）
• 如果我取消注释调试打印，程序seg-faults（这对我来说没有太多意义，但似乎表明我的代码存在缺陷）

我怀疑有一些东西我错过了，一双清新的眼睛可能会抓住。我是否也许错误地处理了这个数组（没有考虑到指针或其他东西的衰变）？

Answer 1

你在纠正这个问题。扭转单链表的正确方法比您想象的要简单得多，而且根本不涉及数组。

您需要做的就是遍历列表，将每个节点的next指针设置为列表头，然后将列表头设置为该节点。实质上，您将取消每个节点的链接并将其插入列表的开头。一旦你到达最后，你的名单就会颠倒过来。

它只是需要一点小心，因为你做事的顺序很重要。像这样的东西应该这样做：

template <class T> 
node<T> * reverse(node<T> * head) 
{ 
    node<T> *current = head; 
    head = NULL; 

    while(current != NULL) 
    { 
     // store remainder of list 
     node<T> *remain = current->next; 

     // re-link current node at the head 
     current->next = head; 
     head = current; 

     // continue iterating remainder of list 
     current = remain; 
    } 

    return head; 
} 

该操作具有线性时间复杂性。你会通过传递列表的头节点如下调用它：

root = reverse(root); 

应该不用说，这将是一个坏主意调用这个函数是不是列表头的任一节点，或者传入包含循环的列表。