Reversing a Link List using Iterative Approach-CodePudding

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.

CodePudding user response：

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;
    }
}

CodePudding user response：

First, a mini code review:

//
// Bigger issues implied by this function are that it is not a very good
// linked list, likely an extremely basic C-style list. However, that is
// beyond the scope of this question.
//
void rev(node* &head)
{
    int flag=0;  // Unnecessary
    node* head1=NULL;  // Prefer nullptr
    while(head->next!=NULL)
    {
        node* temp1=head;
        node* temp2=head;  // Choose better names
        while(temp1->next!=NULL)  // Traverse the entire list at every iteration
        {
            temp2=temp1;
            temp1=temp1->next;
        }
        if(flag==0)
        {
            head1=temp1;
            flag  ;
        }
        temp1->next=temp2;  // Always and only swaps the last two elements
        temp2->next=NULL;

        // Never updates head in the loop; loop is infinite
    }
    head=head1;
    delete head1;  // head1 was pointing to a valid node; you just nuked your
                   // entire list
}

The algorithm is quite simple, and one that reveals itself when the problem is drawn using paper and pencil. You just need to make the arrows point the other way, and reassign the head. You are attempting that, but you don't change any pointers except for the final two nodes. You need to be changing them as you move through the list.

The special head check and flag are unnecessary. You will naturally arrive at the tail and can reassign head when you do so.

Here's the reworked algorithm:

#include <iostream>

struct node {
  int data;
  node* next;

  node(int d) : data(d), next(nullptr) {}
};

//
// Bigger issues implied by this function is that it is not a very good
// linked list, likely an extremely basic C-style list. However, that is
// beyond the scope of this question.
//
void rev(node*& head) {
  node* prev = nullptr;
  node* curr = head;
  node* next = nullptr;  // Not immediately assigned to account for
                         // empty list.

  while (curr) {
    next = curr->next;  //
    curr->next = prev;  // This order of operations is very important
    prev = curr;        //
    curr = next;        //
  }

  head = prev;
}

int main() {
  node* list = new node{1};
  list->next = new node{2};
  list->next->next = new node{3};
  list->next->next->next = new node{4};
  list->next->next->next->next = new node{5};

  node* walker = list;
  std::cout << "Original list: ";
  while (walker != nullptr) {
    std::cout << walker->data << ' ';
    walker = walker->next;
  }
  std::cout << '\n';

  rev(list);
  std::cout << "Reversed list: ";
  walker = list;
  while (walker != nullptr) {
    std::cout << walker->data << ' ';
    walker = walker->next;
  }
  std::cout << '\n';

  // On the one hand, I don't delete my nodes. On the other,
  // the program is ending and the OS will clean up my mess.
  // This is generally a bad practice.
}

Output:

❯ ./a.out
Original list: 1 2 3 4 5 
Reversed list: 5 4 3 2 1

While it would require more code, a proper C linked list class would be strongly preferred to avoid the downright silly initialization required in main().

And I understand that this code is likely just to understand this particular algorithm, but the C standard library does provide both singly and doubly linked lists, both of which are trivial to reverse.