Solved

reversing a linklist

Posted on 2004-10-02
9
272 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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

943 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now