Reversing a Link List using Iterative Approach

Question

What is wrong with my code for reversing a linked list?

void rev(node* &head)
{
    int flag=0;
    node* head1=NULL;
    while(head->next!=NULL)
    {
        node* temp1=head;
        node* temp2=head;
        while(temp1->next!=NULL)
        {
            temp2=temp1;
            temp1=temp1->next;
        }
        if(flag==0)
        {
            head1=temp1;
            flag++;
        }
        temp1->next=temp2;
        temp2->next=NULL;
    }
    head=head1;
    delete head1;
}

I was trying to solve a standard problem of reversing a link list. So i tried implementing this approach, however it seems to be going into infite loop, I am unable to understad why.

Answer 1

Your function is invalid.

For example the passed pointer head can be equal to nullptr. In this case this while loop

while(head->next!=NULL)

already can invoke undefined behavior.

Or there is nothing to delete in the list but the function has these statements

head=head1;
delete head1;

that do not make sense.

Even if to remove the statement with the call of delete nevertheless this does not make the function correct. For example if the list contains only one node then this while loop

while(head->next!=NULL)

will not be executed. As a result the pointer head will be set to NULL due to this statement after the loop

head=head1;

because before the loop the pointer head1 is set to NULL

node* head1=NULL;

Also it seems in this nested while loop

while(temp1->next!=NULL)
{
    temp2=temp1;
    temp1=temp1->next;
}

you are trying to find the last node in the list that at least is inefficient.

And your function is unclear and too complicated.

To write the function it is enough to learn the standard C++ function std::exchange declared in header <functional> that will make the code of the function more simpler and clear.

Here is a demonstration program that shows how the function that reverses a singly-linked list can be implemented.

#include <iostream>
#include <functional>
#include <iterator>

struct node
{
    int data;
    node *next;
};

void clear( node * &head )
{
    while ( head ) delete std::exchange( head, head->next );
}

void assign( node * &head, const int a[], size_t n )
{
    clear( head );

    for (node **current = &head; n--; current = &( *current )->next)
    {
        *current = new node{ *a++, nullptr };
    }
}

std::ostream & display( const node *const &head, std::ostream &os = std::cout )
{
    for (const node *current = head; current != nullptr; current = current->next)
    {
        os << current->data << " -> ";
    }

    return os << "null";
}

void reverse( node * &head )
{
    for ( node *current = head, *previous = nullptr; current != nullptr; previous = head )
    {
        head = std::exchange( current, current->next );
        head->next = previous;
    }
}

int main()
{
    node *head = nullptr;
    const int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    assign( head, a, std::size( a ) );

    display( head ) << '\n';

    reverse( head );

    display( head ) << '\n';

    clear( head );
}

The program output is

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null

As you can see the function has only one for loop the compound statement of which contains only two statements

void reverse( node * &head )
{
    for ( node *current = head, *previous = nullptr; current != nullptr; previous = head )
    {
        head = std::exchange( current, current->next );
        head->next = previous;
    }
}

Without using the standard function std::exchange the function that reverses a list will have one more statement as for example

void reverse( node * &head )
{
    for ( node *current = head, *previous = nullptr; current != nullptr; previous = head )
    {
        head = current;
        current = current->next; 
        head->next = previous;
    }
}