Help: reverse a linked list

{ Multi-posted to clc++, where the author followed up with "Fixed it myself,
thanks." -mod }

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.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 7 sep, 13:28, Hamster <freehamster2...@gmail.com> wrote:

> Need help with my code on reversing a singly linked list

The best way to reverse any sequence is probably to use a range
adaptor that reverses it on the fly.
You do not mutate the original sequence, you do not allocate memory
for a new one, and it's a constant-time operation.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

The best way to solve such problem is to do dry run.

p1.nextPtr = 0 ;
while (P3 != 0 )
{
p2->nextPtr= p1;
p1 = p2;
if ( p3!= 0 ) p2 = p3;
p3 = p3->nextPtr;
}
p2.nextptr = p1;


To see how list works, then its fine to try such code. To use in any
professional coding, go for STL list instead of creating a new one.

#include <list>
#include<iostream>

using std::cout;
using std::endl;

int main(int argc, char **argv)
{
std::list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);

for( std::list<int>::const_iterator it = l1.begin(); it !=
l1.end() ; ++it)
{
cout <<"loop in same direction" <<*it<<endl;
}
for( std::list<int>::reverse_iterator it = l1.rbegin(); it !=
l1.rend() ; ++it)
{
cout <<"loop in opp direction" <<*it<<endl;
}

// now actual reverse the list.. not just loop direction
std::reverse(l1.begin() , l1.end());
for( std::list<int>::const_iterator it = l1.begin(); it !=
l1.end() ; ++it)
{
cout <<"loop in same direction after reverse" <<*it<<endl;
}
for( std::list<int>::reverse_iterator it = l1.rbegin(); it !=
l1.rend() ; ++it)
{
cout <<"loop in opp direction reverse" <<*it<<endl;
}
}


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 7 Set, 17:58, Mathias Gaunard <loufo...@gmail.com> wrote:
> On 7 sep, 13:28, Hamster <freehamster2...@gmail.com> wrote:
>
> > Need help with my code on reversing a singly linked list
>
> The best way to reverse any sequence is probably to use a range
> adaptor that reverses it on the fly.
> You do not mutate the original sequence, you do not allocate memory
> for a new one, and it's a constant-time operation.
>

Ahem, that would be quite hard to do with an adaptor. The list is
singly linked, thus it supports only forward iteration.

--
gpd

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

on Sun Sep 07 2008, Mathias Gaunard <loufoque-AT-gmail.com> wrote:

> On 7 sep, 13:28, Hamster <freehamster2...@gmail.com> wrote:
>
>> Need help with my code on reversing a singly linked list
>
> The best way to reverse any sequence is probably to use a range
> adaptor that reverses it on the fly.
> You do not mutate the original sequence, you do not allocate memory
> for a new one, and it's a constant-time operation.

A singly-linked list? How does that work without allocations?

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 8 sep, 15:36, gpderetta <gpdere...@gmail.com> wrote:

> The list is
> singly linked

I have to admit I didn't pay attention to that.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Sep 7, 6:28Â am, Hamster <freehamster2...@gmail.com> wrote:
> { Multi-posted to clc++, where the author followed up with "Fixed it myself,
> thanks." -mod }
>
> Hi,
>
> Need help with my code on reversing a singly linked list, here's  my
> code:

Reducing the number of book-keeping pointers will help to simplify the
code. Here is my attempt. This is untested code.

void reverseList(List& obj)
{
ListNode *newHead = 0;
ListNode *cur = obj.firstPtr;
obj.lastPtr = obj.firstPtr;

while ( cur != 0 ) {
ListNode* tmpNext = cur->nextPtr;
cur->nextPtr = newHead;
newHead = cur;
cur = tmpNext;
}
obj.firstPtr = newHead;
}

Rgds,
anna

--
Abusive Language on the Internet
http://missingrainbow.blogspot.com/2...-internet.html


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]