我正在尝试创建一个函数,更改节点指针的顺序,以便反转原始列表。
我的解决方案是基于对主列表进行迭代,然后反转每两个相邻节点的顺序:第一次迭代后,(n1)->(n2)
将是(n1)<-(n2)
。
我的尝试:
Node push1(Node* curr) {
if(curr == NULL || *curr == NULL) {
return NULL;
}
Node temp = (*curr)->next;
if(temp == NULL) {
return NULL;
}
(*curr)->next = *curr;
return temp;
}
/*******************************/
void reverse2(Node* head) {
Node curr = *head;
while(curr != NULL) {
curr = push1(&curr);
}
}
问题:我运行了一个无穷大循环。我试着解决了这个问题,但列表没有颠倒顺序。有没有一种方法可以使用push1()
的这种方法?
注意:我不是在寻找3指针或递归的解决方案。
这很有效,但有点傻
Node* push1(Node** prev, Node* curr)
{
Node* ret = curr->next;
curr->next = *prev;
(*prev)=curr;
return ret;
}
void reverse2(Node** head)
{
Node* prev = *head;
if(!prev) return;
Node* curr = prev->next;
if(!curr) return;
prev->next = 0;
while(curr)
{
curr = push1(&prev,curr);
}
*head = prev;
}
这是不可读或可移植的,但它不使用递归或其他变量:
struct list {
list *next;
/* ... */
};
list *
reverse(list *l)
{
list *head = nullptr;
while (l) {
head = (list *) ((uint64_t) head ^ (uint64_t) l->next);
l->next = (list *) ((uint64_t) l->next ^ (uint64_t) head);
head = (list *) ((uint64_t) head ^ (uint64_t) l->next);
l = (list *) ((uint64_t) l ^ (uint64_t) head);
head = (list *) ((uint64_t) head ^ (uint64_t) l);
l = (list *) ((uint64_t) l ^ (uint64_t) head);
}
return head;
}
诀窍是使用xor
交换。
使用std::stack<>非常容易数据结构与std::vector<>相结合。回想一下,Stacks是一种容器,设计用于在后进先出(后进先出)环境中操作,其中元素仅从容器的一端插入和提取。
因此,在您的情况下,您将创建一个堆栈,按照现有的顺序将节点添加到堆栈中,然后将它们从堆栈中弹出,这与节点的顺序相反。
我已经草拟了代码来做这件事,但请注意,它没有经过测试,你应该能够根据你的情况调整这个想法:
#include <stack>
#include <vector>
std::vector<Node> reverseNodes(Node* currNode, Node* startNode) {
std::vector<Node> reversed;
std::stack<Node> nodeStack;
// First add nodes to the stack:
for (Node* aNode = currNode; aNode != startNode; aNode = aNode->next) {
nodeStack.push(aNode);
}
// Next add your starting node to the stack (last-in):
nodeStack.push(startNode);
// Popping off of the stack reverses the order:
while (!nodeStack.empty()) {
reversed.push_back(nodeStack.pop());
}
// Return the nodes ordered from last->first:
return reversed;
}