Binary01
Binary01

Reputation: 245

Reverse linked list causes a loop

Why does this cause a loop?

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

Answers (1)

Maxim Egorushkin
Maxim Egorushkin

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

Related Questions