Search code examples
c++pointerslinked-list

Not Equal to operator on pointer


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.


Solution

  • 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.