Solved

Reverse linked list

Posted on 2007-03-21
4
1,309 Views
Last Modified: 2012-08-13
I am trying to create a function to reverse a linked list.  The function should have one parameter which is a head pointer to the linked list.. The function should modify the linked list pointed to by its parameter by reversing the order of the items in the list....

Could someone give me some insight on this?  This is homework so I am not really looking for code, but algorithm information would be helpful...  I have been staring at this problem for far too long now and I know it isn't very difficult...
0
Comment
Question by:brassmon
[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 Comments
 
LVL 6

Expert Comment

by:bijopuli
ID: 18766026
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 250 total points
ID: 18766056
Just traverse the linked list from beginning to end, and invert the links.

Suppose you have a list :

    elem1 -> elem2 -> elem3 -> ...

Then you start at the beginning :

    elem1 -> elem2 -> elem3 -> ...
       ^

And come to this situation :

    elem1 <- elem2 -> elem3 -> ...
                      ^

And then you can do the same thing for the link between elem2 and elem3, etc.

Does that get you started ?

Can you give it a try, and post some code ?
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 250 total points
ID: 18766198
>>>> I am trying to create a function to reverse a linked list.  
I assume it is a singly linked list. If so, you should nevertheless add a member pointer for the tail node and not only the head node cause a tail node has a lot of advantages. So, you can add at the front or back and for the task to reverse the list you need the pointer to the tail node as well.

Reversing a linked list mostly is done by calling a recursive member function of the node strcut/class. It  takes a pointer to the previous node as argument. The implementation of the recursive function firstly checks whether the next pointer is not NULL. If so, it calls the next->reverse function  recursively usiing the this as argument: After the call it assigns the parenet pointer to the next pointer:
   
Sample:

    1  -> 2 -> 3 -> 4 -> 5

you would call 1->reverse passing NULL and 1 is the head node pointer. The headpointer would call 2->reverse passing this what is 1 what is the head pointer. (2)->reverse would call (3)->reverse(2) passing node 2,  (3) ->reverse would call (4)-reverse(5) because (4)->next == 5. (5)->reverse would stop recursion cause (5)->next is NULL. (5)->reserve would assign (4) to (5)->next and return. (4)->reserve would continue (after 5->reserve() has returned) and would assign (3) top (4)->next, ... and so on, (1)->reverse() would assign NULL to (1)->next, what means that (1) is the new tail now.

Finally you have

   (1) <- (2) <- (3) <- (4) <- (5)

what is a reverse list. The list becomes valid after you exchanged the head node pointer by the former tail node pointer. That's why it would be good if you already have both head and tail. If not, you either need to get the tail node by an additional loop prior to calling the reverse function or you let the reverse function return a node pointer wich was assigned by the very last recursive call when the enxt pointer was NULL. Then the reverse function returns this and all other reverse calls return the same pointer so that finally the linked list has the new head pointer:

class LinkedList
{
    Node* head;
    ....

    void reverse() { if (head) head = head->reverse(NULL); }
     ...
};

Regards, Alex
0
 
LVL 16

Expert Comment

by:AlexNek
ID: 18766765
As it is the homework you can try to realize some diferent algortihms or at least thinking about.
I think, the quickest way is a C-Style algorithm where you scan a list via loop or recursivelly.
In C++ style, in my opinion, it must be an iterator class for scan the list. In addition you must not forgot about the root. If before start it pointed to original head, then after end it must be pointed to original tail.
For imagination, add one fictive NULL item "before" head, then swap the pointers /a linked to b, then b must be linked to a/ and go to the next item. You see, you must to work with two items simultaneously and get the next item before you swap the links.
0

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Which IDE to use to begin C++ training? 5 76
Template syntax for variable length arrays 9 79
Best book to learn C++ 4 97
Gaming Software 1 38
In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

738 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