反向链表会导致循环

Question

为什么会导致循环

我试图使用迭代方法创建反向链表，但当遍历头节点时会发生循环(例如print(((。我在C#中尝试过，没有遇到任何问题(当然修改了语法(。

struct Node {
int data;
Node* next;
};
void
Reverse(Node& head_ref) {
Node* current = &head_ref, *next = nullptr, *prev = nullptr;
while (current != nullptr) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head_ref = *prev; //strange phenomenon happened here after head_ref is set.
}
int
main() {
Node* head = new Node();
Node* first = new Node();
head->data = 1;
head->next = first;
first->data = 2;
first->next = nullptr;
Reverse(*head);
while (head != nullptr) { // <-- infinite loop
cout << head->data << endl;
head = head->next;
}
return 0;
}

---

prev中的变量反向(…(返回时的方法：

0x0108ed10 {data=2 next=0x00eff190 {data=1 next=0x00000000 <NULL> } }
data: 2
next: 0x00eff190 {data=1 next=0x00000000 <NULL> }

设置head_ref后，它会创建一个循环链表：

0x0108ed10 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {...} } } } }
data: 2
next: 0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {data=2 next=0x00eff190 {...} } } } }

Answer 1

head_ref = *prev;覆盖Node，因为head_ref是Node&，而不是Node*&。鉴于您打算更新head指针，而不是整个Nodehead_ref引用。

一个解决方案是：

void Reverse(Node*& head) {
Node* current = head;
// ...
head = prev;
}
// ...
Reverse(head);

或者：

Node* Reverse(Node* head) {
Node* current = head;
// ...
return prev;
}
// ...
head = Reverse(head);