Help: reverse a linked list

Hi,

Need help with my code on reversing a singly linked list, here's my
code:

void reverseList ( List& listObj)
{

ListNode*pHeadnew=listObj.lastPtr, *pTailnew=listObj.firstPtr;

ListNode* p1=listObj.firstPtr, *p2=listObj.firstPtr->nextPtr, *p3=p2-
>nextPtr;

while (p3!=0)
{
p2->nextPtr=p1;
p1=p2;
p2=p3;
p3=p3->nextPtr;
}

listObj.firstPtr=pHeadnew;
listObj.lastPtr=pTailnew;
listObj.lastPtr->nextPtr=0;
}

My test code created a 5-node list, after calling this function
(declared as friend in class List), the resulting list has only 1 node
left.

May anyone help spot what is wrong?

Thanks.

On Sun, 07 Sep 2008 01:41:08 -0700, Hamster wrote:

> Fixed it myself, thanks.
>
> Is there any way to delete your own post?

If you're religious, you could beg to your deity of choice.
The answer is no, your post is forever archived.

--
OU

Fixed it myself, thanks.

Is there any way to delete your own post?

* Hamster:
>
> Need help with my code on reversing a singly linked list, here's my
> code:
>
> void reverseList ( List& listObj)
> {
>
> ListNode*pHeadnew=listObj.lastPtr, *pTailnew=listObj.firstPtr;

As a matter of style, in C++ try to preferentially declare only one thing per
declaration. This allows you to focus on types. Which is what C++ is about.

ListNode* pHeadNew = listObj.lastPtr;
ListNode* pTailNew = listObj.firstPtr;

It also helps to inform the reader (and the compiler) that those variables will
not be modified after initialization,

ListNode* const pHeadNew = listObj.lastPtr;
ListNode* const pTailNew = listObj.firstPtr;


> ListNode* p1=listObj.firstPtr, *p2=listObj.firstPtr->nextPtr, *p3=p2-
>> nextPtr;

Since the p2 declarator dereferences firstPtr, firstPtr can't be 0. Hence your
list structure has a dummy first node that's always present, generally called a
"header node". Since the p3 declarator also dereferences firstPtr->nextPtr, you
either have a circular list or a dummy always-present last node, which we may
call a "tail node". The use of != as loop condition means you do not have a
circular list. Hence, if the code so far is correct, you have a singly linked
list with always-present "header node" and "tail node".

You should have explained that.

If you do not have a list with always present "header node" and "tail node",
then the code is simply wrong, since that's what it requires.


> while (p3!=0)
> {
> p2->nextPtr=p1;
> p1=p2;
> p2=p3;
> p3=p3->nextPtr;
> }

This seems technically OK provided the list structure is as described above.


> listObj.firstPtr=pHeadnew;
> listObj.lastPtr=pTailnew;
> listObj.lastPtr->nextPtr=0;

Think about a logically empty list, one with only "header node" and "tail node".
For that case the above forgets to do one important thing.


> }
>
> My test code created a 5-node list, after calling this function
> (declared as friend in class List), the resulting list has only 1 node
> left.

That conclusion seems to be incorrect. You forget that your incorrect reverse
function does not necessarily leave you with a valid list structure (see above).
A correct function should always leave you with a valid list, if it's fed one.


Cheers & hth.,

- Alf

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Alf,

I missed some if/else structure when copying/pasting which left that
piece of code logically incomplete and confusing.

Thank you for your time.

OU,

Thanks to confirm...would be nice if there were such a feature, imo.

"Hamster" <freehamster2008@gmail.com> wrote in message
news:7bb690da-eb68-4783-ade0-9e900d03c28c@p10g2000prf.googlegroups.com...
> Hi,
>
> Need help with my code on reversing a singly linked list, here's my
> code:
__________________________________________________ ______
node* reverse(node* list) {
node* head = NULL;
while (list) {
node* const next = list->next;
list->next = head;
head = list;
list = next;
}
return head;
}
__________________________________________________ ______

"Chris M. Thomasson" <no@spam.invalid> writes:

> "Hamster" <freehamster2008@gmail.com> wrote in message
> news:7bb690da-eb68-4783-ade0-9e900d03c28c@p10g2000prf.googlegroups.com...
>> Hi,
>>
>> Need help with my code on reversing a singly linked list, here's my
>> code:

node* reverse1(node* list,node* result){
if(list){
node* next=list->next;
return(reverse1(next,(list->next=result,list)));
}else{
return(result);
}
}
node* nreverse(node* list){
return(reverse1(list,0));
}
// Notice that g++ -O3 implements TCO, so there's no recursive call here.


With better definitions it could be written as:

node* reverse1(node* list,node* result){
return(list?reverse1(rest(list),cons(first(list),r esult)):result); }
node* reverse(node* list){
return(reverse1(list,0)); }
// Still no recursive call, thanks to TCO.


that is:

struct node {
char* first;
node* rest;
node(char* aFirst,node* aRest):first(aFirst),rest(aRest){};
};

char* first(node* node){return(node->first);}
ndoe* rest(node* node){return(node->rest);}
node* cons(char* first,node* rest){return(new node(first,rest));}



> __________________________________________________ ______
> node* reverse(node* list) {
> node* head = NULL;
> while (list) {
> node* const next = list->next;
> list->next = head;
> head = list;
> list = next;
> }
> return head;
> }
> __________________________________________________ ______

This works ok, so what else do you want?

--
__Pascal Bourguignon__

On Sun, 7 Sep 2008 01:41:08 -0700 (PDT), Hamster <freehamster2008@gmail.com> wrote:
> Fixed it myself, thanks.
>
> Is there any way to delete your own post?

There used to be, but people started disabling it fifteen years ago
due to abuse. It's called /cancelling/ a posting.

In either case, it's more polite to show us your error and the
solution.

/Jorgen

--
// Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
\X/ snipabacken.se> R'lyeh wgah'nagl fhtagn!