?
Solved

reversing a linklist

Posted on 2004-10-02
9
Medium Priority
?
333 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 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
The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

 
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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

590 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