Solved

reversing a linklist

Posted on 2004-10-02
9
295 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 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
Technology Partners: 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 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

Independent Software Vendors: 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!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Compile GLUT with Visual Studio 2015 1 207
best sources to up-to-date in C++? 8 104
Best book to learn C++ 4 87
Error C2678: binary '!=': no operator found... 4 65
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…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

726 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