I have written the following reverse function for reversing a linked list, given the first and last node addresses of the linked list. The next member data of the last node may or may not be equal to NULL.
I want the while to terminate when first equals to last->next. But it keeps going.
#include <iostream>
using namespace std;
struct node
{
int data{};
node *next{};
node() = default;
node(int d, node *n) : data(d), next(n) {}
};
void reverse(node *first, node *last)
{
node *temp = nullptr;
node *nextNode = nullptr;
while (first != last->next)
{
nextNode = first->next;
first->next = temp;
temp = first;
first = nextNode;
}
}
int main()
{
//creation of linked list
node *n4 = new node(4, nullptr), *n3 = new node(3, n4), *n2 = new node(2, n3), *n1 = new node(1, n2);
reverse(n1,n4); //call to reverse function
node *temp = n4; //printing linked list for debugging
while (temp)
{
cout<< temp->data;
temp = temp->next;
}
return 0;
}
The function can also be written as follows
void reverse(node *first, node *last)
{
node *temp = nullptr, *nextNode;
while (first != last)
{
nextNode = first->next;
first->next = temp;
temp = first;
first = nextNode;
}
first->next=temp;
}
and the code run perfectly.
I added the following to your code to see what happens to the pointers in the while loop
cout << first << ' ' << last->next << ' ' << (first != last->next) << '\n';
while (first != last->next)
{
nextNode = first->next;
first->next = temp;
temp = first;
first = nextNode;
cout << first << ' ' << last->next << ' ' << (first != last->next) << '\n';
}
The output was
000001D844AF1A80 0000000000000000 1 000001D844AF1EE0 0000000000000000 1 000001D844AF2610 0000000000000000 1 000001D844AF1E90 0000000000000000 1 0000000000000000 000001D844AF2610 1
As you can see the pointer comparison is working perfectly correctly. The actual problem is that, as you can see in the last line, first
becomes equal to nullptr
but last->next
changes at the same time.