Redirect a simple linked list

[dragost]

Hello all.

I've just succeeded in creating a recursive function which
redirects a simple linked list ... but ...

I'm wondering if there exists a better recursive function to redirect a simple linked list ... (i still believe that the answer is NO)

Example:
If we have the list:
Node1->Node2->Node3
The redirected list is:
Node3->Node2->Node1

My very simple program is:

#include <stdio.h>

typedef struct tagNODE
{
int info;
tagNODE* next;
} NODE;

void Listing(NODE* node)
{
while (node)
{
printf("%d\n", node->info);
node = node->next;
}
}

NODE* Redirect(NODE* parent, NODE* node)
{
if (node->next == NULL)
{
node->next = parent;
return node;
}
else
{
NODE* p = Redirect(node, node->next);
node->next = parent;
return p;
}
}

void main(void)
{
NODE *node1 = new NODE, *node2 = new NODE;
NODE *node3 = new NODE, *node4 = new NODE;

node1->info = 1;
node2->info = 2;
node3->info = 3;
node4->info = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;

Listing(Redirect(NULL, node1));
}

Thanks a lot...

Dragos

[DanM]

You may want to take a look at the std::reverse (in <algorithm>).

Here is the STL equivalent of your code:

#include <list>
#include <algorithm>

using namespace std;

list<int> list1;

list1.insert(list1.end(), 1);
list1.insert(list1.end(), 2);
list1.insert(list1.end(), 3);
list1.insert(list1.end(), 4);

reverse(list1.begin(), list1.end());

Dan

[dragost]

Hello again

NOTE: You should be interested in the problem i talked about..
It's a problem (not so simple) from MICROSOFT interviews...


I' ve just studied the file 'algorithm' and there the function
'reverse' is not recursive, as i wanted. Also, this function uses
a function named '_Reverse', which is not recursive. It just uses
iterators to swap the nodes of the list.

It's clear that 'reverse' is a very good function; but my function
doesn't uses iterators...and is recursive.

So, my question remains available:
"Do you now a more efficient function that is recursive ?"

[dragost]

Hello again

NOTE: You should be interested in the problem i talked about..
It's a problem (not so simple) from MICROSOFT interviews...


I' ve just studied the file 'algorithm' and there the function
'reverse' is not recursive, as i wanted. Also, this function uses
a function named '_Reverse', which is not recursive. It just uses
iterators to swap the nodes of the list.

It's clear that 'reverse' is a very good function; but my function
doesn't uses iterators...and is recursive.

So, my question remains available:
"Do you know a more efficient function that is recursive ?"

[j0nas]

First, no I don't know of any faster recursive function (I haven't really tried either)... But recursive functions are more oftan slower than iteratives.

Maybe you can improve speed little by trying this:
1. Use the 'const' keyword infront of parameters and/or variables that don't change. This may improve compiler optimization.
2. Try to redesign the function so it only takes on 1 parameter. For large lists (1000+ items(!)), this may improve function call time (reduce overhead).

[galathaea]

I think a good answer for a Microsoft interview about this would be

Well, if you need to reverse a linked list even once, I would just use a doubly linked list. Since reversing nodes is an O(n) process, that completely counteracts the doubling in time of building a doubly linked list if you use it once, and any more uses are free!

But I might replace the pointers in the parameter passing and return of your recursive function with references to avoid the unnecessary temporary copy semantics... However, always do profiling to see how your compiler reacts!

[galathaea]

Also, if you know at compiletime the elements of the linked list (like in your example), some generic programming can help you immensely here. Then, you can make a compiletime forward version and a compiletime reverser that, by the necessities of template type dynamics, must be recursive!

[DanM]

1) Replacing pointers with references is not really a good ideea.
What do you do with NULL pointers ? (I know an answer but it is not more efficient than the originla implementation).

2) MS interviewers do not care about fancy design issues and answers that do not exactly address their questions. The purpose of the interview (at least for a junior engineer) is to figure out if he has the potential to properly do his job. He may end up doing driver development and then all the template stuff is useless. A fast/optimized algorithm - that's what it matters...

2) Dragos, you may want to take a look at this one (it reverses a string but your problem is very similar):

http://groups.google.com/groups?q=%22Microsoft+interview%22+reverse+list&hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=330e5a74.80470722%40la-news1.digilink.net&rnum=3


Dan

[galathaea]

2) MS interviewers do not care about fancy design issues and answers that do not exactly address their questions. The purpose of the interview (at least for a junior engineer) is to figure out if he has the potential to properly do his job. He may end up doing driver development and then all the template stuff is useless. A fast/optimized algorithm - that's what it matters...

But that's exactly my solution -- a doubly-linked list! That is the only proper way to answer this question, for all the reasons I have mentioned above. If you are dealing with a singly-linked list and need to reverse it, you are dealing with the wrong type of data structure. I am completely positive that Microsoft does not want someone doing things incorrectly just because they didn't want to "shake the boat". This is a basic concept in data structures, and if you point it out to them in an interview, it shows that you have a grasp of the fundamentals of algorithmic complexity theory.

The template solution is technically the fastest if the list is known at compiletime, since the reverse is done at compiletime, and there is therefore no runtime spent on the problem!!! Of course, this is likely not the case in the real interview (where I am sure they ask for doing something with a runtime generated list or something), but the OP could be solved this way and I felt that it was a good point to make.

As for the references, I am not sure whether dereferencing the pointer and passing by reference would be faster than the copy semantics of a POD, but I do know that passing by reference can be faster than passing by pointers in tight loops. And a properly placed try-catch could make no if check necessary, but unwinding the stack can be slow (although you really only need to do the unwinding for one stack frame -- the innermost last link which can handle it itself to indicate list termination). All of these considerations are why it is important to do profiling to see if there is a benefit.

And finally, it is important to point out that the link that DanM provided shows only strings (which are not linked list structures) recursively and circular lists iteratively. So I do not think they may be relevant to the problem (particularly when changing the strings recursion for linking leads to similar code as the OP).

But more importantly. DanM, I have noticed you have been acting quite belligerantly towards me ever since I supported a comment by kuphryn in an alternate post. I am sorry if my posts have ever offended you, but I do not believe I have ever referred to you once in my posts. And I appologize if I am mistaking your attitude here, but I am concerned.

[DanM]

I'm not acting belligerantly :)
I just figured out that some of your posts fail to address the initial question with a direct/clear/noncomplicated answer when that answer exists.
I think the purpose of this message board is to help people to solve their problems and not to engage in endless theoretical discussions.

That's all.

Dan

[galathaea]

But my post gave a concrete answer to the OP. In fact, it gave three. I stated which one was the best. I do not understand what is wrong with my posts. I am always willing to give specific implementations, where appropriate, and I do quite often. I am sad you continue to think that I have little real world knowledge to offer, but I guess its not appropriate to discuss it any furthur.

:(

[DanM]

Somehow, I get the feeling the MS interviewer is also familiar with the double linked list... But his purpose is to test your ability to write a very efficient algorithm not to use a different data structure and radically change the algorithm which becomes trivial in this case. And the option to choose a single linked list may be (in the real world :) ) justified by some other considerations like memory usage,insertion/deletetion speed and so on ...

I think more posts on the same subject won't help the original poster too much so I'll stop here.

Happy New Year to all of you !

Dan

[galathaea]

I think the point about a doubly-linked list here is still relevant. It would not be wise to use a recursive function in the first place if memory is a concern, and that would be the only difference between the singly- and doubly-linked lists (not just with the function overhead, but also all the temporaries -- here, p -- that are created in the recursion). As my earlier post stated, if you ever need to reverse a singly-linked list, then you have already compensated (and surpassed, in fact, considering the list data) for any decrease in insertion speed. Switching the direction of links in a linked list is an O(N) operation, because every pointer link (next) must be switched. Therefore, insertion speed is never an issue if you need to switch even just once.

These are the points I have been trying to make concerning such a Microsoft interview. Of course, the interviewer knows about the doubly linked list (at least I hope so!). But does the interviewee? If you point out that this type of design problem is better implemented other than the suggestion, and give a full, reasoned explanation of why, then I see no interviewer taking this as a bad thing ever, since this is classic problem solving (and I would suspect that this was what was wanted in the first place -- it demonstrates a good knowledge of basic data structures, algorithmic complexity, and design optimization, all of which would seem to me to be the point of the interview). Of course, if the intent of the question is to focus on a different skill set, then the interviewer can mention this, and one can wow them with the alternate skills as well. It is a good thing to let the interviewer know your full range of capablities.

[Andreas Masur]

Originally posted by DanM
2) MS interviewers do not care about fancy design issues and answers that do not exactly address their questions. The purpose of the interview (at least for a junior engineer) is to figure out if he has the potential to properly do his job. He may end up doing driver development and then all the template stuff is useless. A fast/optimized algorithm - that's what it matters...

Well...I never was at an interview with Microsoft (and I NEVER will be) but if the above statement is true, then this would at least explain why they develop as they do and why the results are that bad, slow, whatever... :cool:

PS: BTW...galathaea could cou check your private messages...

[Cheesus]

The STL list tempalte provides a reverse_iterator type. Start at rbegin() and finish at rend(). If the data structure is flat then recursing it will be slow and limit you to a maximum amount of members (due to the stack size).