Solved

reversing a linklist

Posted on 2004-10-02
9
282 Views
Last Modified: 2010-04-01
Hi how do I reverse a linklist, I tried making a reverse function based on the idea that I should swap the pointers. But wasn't able to implement it properly.

I actually want to reverse the same list instead of creating a templist and then adding to it the values of the original list and then destroying the list.

Last thing I need to know is how to overload the = operator which sets one linklist equal to another

------------------------------
#include "iostream.h"

struct link
{

      int x;
      link *next;

};

class linklist
{

      link * first;
public:
      linklist()
      {
            first=NULL;
      }

      void additem(int d);
      void display();
      void reverse();
};

void linklist::additem(int d)
{
 
      link *nextlink = new link;
      nextlink->x=d;
      nextlink->next=first;
      first=nextlink;



}

void linklist::display()
{

      link *current=first;

      while (current !=NULL)
      {
      
            cout << current->x <<endl;
            current=current->next;
      }

}


void linklist::reverse()

{
      link *current=first;
      link *temp=NULL;
      link *count;

      //int temp=0;

      cout <<"first= " << first <<endl;

      while(count !=NULL)
      {
      
            temp=current;
            current=current->next;
            current->next=temp;
            count=current->next->next;
      }

}


void main()
{

      linklist li;

      li.additem(5);
      li.additem(43);
      li.additem(86);

      li.reverse();
      
      li.display();


}
0
Comment
Question by:anshuma
  • 4
  • 3
  • 2
9 Comments
 
LVL 15

Expert Comment

by:efn
ID: 12208840
An algorithm for reversing a linked list:

while the source list is not empty
{
  remove the first element from the input list
  add the element to the beginning of the output list
}

An algorithm for assigning to a linked list:

clear the target list
start at the beginning of the source list
while not at the end of the source list
{
  make a copy of the current source element
  add the copy to the end of the target list
  advance to the next source element
}

Or were you looking for the syntax for declaring an assignment operator?
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12208851
This is my first attempt (not tested):

link *invert_list(link *node, link *prev)
{
   if (node->next)
         invert(node->next, node);
   else
         node->next = prev;
   return node;
}

0
 
LVL 55

Assisted Solution

by:Jaime Olivares
Jaime Olivares earned 125 total points
ID: 12208894
Ok, I got it. I'll send full code. Please advice if any problem.

#include <iostream>

using namespace std;

struct link
{
     int x;
     link *next;
};

link *invert_list(link *node, link *prev)
{
    link *last;

   if (node->next)
         last = invert_list(node->next, node);
   else
         last = node;
         
   node->next = prev;
   return last;
}


class linklist
{
     link * first;
public:
     linklist()
     {
          first=NULL;
     }

     void additem(int d);
     void display();
     void reverse();
};

void linklist::additem(int d)
{
     link *nextlink = new link;
     nextlink->x=d;
     nextlink->next=first;
     first=nextlink;
}

void linklist::display()
{
     link *current=first;

     while (current !=NULL)
     {
          cout << current->x <<endl;
          current=current->next;
     }
}

void linklist::reverse()
{
    first = invert_list(first, NULL);
}

int main()
{
     linklist li;

     li.additem(5);
     li.additem(43);
     li.additem(86);

     cout << "Normal" << endl;
     li.display();
     li.reverse();
     cout << "Reversed" << endl;
     li.display();
   
     return 0;
}
0
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 
LVL 15

Expert Comment

by:efn
ID: 12208993
>  Please advice if any problem.

With a sufficiently large list (11,000 was enough when I tested), the program blows up with a stack overflow.  This might be considered a problem.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12209007
Memory comsumsion and performance always are compromised. Just choose the right for you.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12209057
quicksort for a huge  list or array also can fail due its recursive nature. If you plan to reverse a huge linked list, then you can divide it in portions, inverse every portion and link all them again. But I would do it only if strictly necessary.
0
 
LVL 11

Accepted Solution

by:
bcladd earned 125 total points
ID: 12209425
My argument against jaime_olivares' argument is that in this case there is an equally easy to write ITERATIVE solution. Quicksort is much harder to rewrite iteratively.

Try:

void reverse()
{
  node* prev = NULL, * curr = head;
 
  while (curr != NULL) {
    node * next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  head = prev;
}


-bcl
0
 
LVL 15

Expert Comment

by:efn
ID: 12209674
bcladd's solution, which is equivalent to the one I outlined above, is preferable because it requires storing 3 pointers rather than 2n pointers.  I consider this more significant than the fact that it is iterative, although that also saves memory.  From my experience trying to code this in job interviews, I think bcladd's solution, while not conceptually difficult, is actually harder to write than jaime_olivares's solution.
0
 
LVL 11

Expert Comment

by:bcladd
ID: 12209761
No question the recursive solution is the easier one to think through. It is not hard to work it around to being tail recursive and then rewriting it iteratively is actually mechanical (there are compilers that can optimize tail recursion into a loop). The solution I wrote was not based on a tail recursive solution (I just worked through it and tried to remember how it worked; I am going to have to assign something like this in the next week so most of this is fresh in my mind).

-bcl
0

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Implementing a ResolveEventHandler in C++ 13 133
Load and store *.pnm image file 1 86
Focus not getting shifted out of  editbox 2 63
Embarcadero C++ Builder XE2 TDateTime 8 71
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question