Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

reversing a linklist

Posted on 2004-10-02
9
Medium Priority
?
315 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 500 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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 500 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

On Demand Webinar: Networking for the Cloud Era

Ready to improve network connectivity? Watch this webinar to learn how SD-WANs and a one-click instant connect tool can boost provisions, deployment, and management of your cloud connection.

Question has a verified solution.

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

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

670 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