Reputation: 245
I am trying to do a reverse linked list using an iterative method, but a loop occurs when the head node is traverse (ex. print()). I've tried this with C# and had no problem (modified syntax of course).
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 variable in Reverse(...) method on return:
0x0108ed10 {data=2 next=0x00eff190 {data=1 next=0x00000000 <NULL> } }
data: 2
next: 0x00eff190 {data=1 next=0x00000000 <NULL> }
After head_ref is set it creates a cycle linked list:
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 {...} } } } }
Upvotes: 1
Views: 103
Reputation: 136306
head_ref = *prev;
overwrites a Node
because head_ref
is Node&
, not Node*&
. Whereas you intend to update head
pointer, rather than an entire Node
head_ref
refers to.
One fix would be:
void Reverse(Node*& head) {
Node* current = head;
// ...
head = prev;
}
// ...
Reverse(head);
Alternatively:
Node* Reverse(Node* head) {
Node* current = head;
// ...
return prev;
}
// ...
head = Reverse(head);
Upvotes: 1