Reverse Linked list [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 8 years ago.

I'm implementing a linked list with pointers.
I need to reverse the linked list, so I wrote rotate(List &l)
but i don't get the result I expect.
Since input is
0 1 2 3 4 5 6 7 8 9
i would expect
9 8 7 6 5 4 3 2 1 0
as a result, but i get
0 9 8 7 6 5 4 3 2 1

Since I can't find what I did wrong, can you point me at what is incorrect? the problem seems to start here: (rotate)

while(end->next !=0){
       end = end->next;
    }

I get there that the first node is the last node (since cout << end->d; gives me0 instead of 9)

#include<iostream>

using namespace std;

typedef class Node *List;
struct Node{ 
    int d;
    List next;
};
//update : renamed
void reverse(List &l){
/*
start :
a b c d e

b c d e **a**
c d e **b** a
d e **c** b a
Result:
e **d** c b a
    */

    // get last node
    List end = l;
    while(end->next !=0){
       end = end->next;
    }
    //insert first node directly after the original last node
    while(l!=end){
        List hulp = l;
        l = hulp->next;
        hulp->next = end->next;
        end->next=hulp;
    }
}
int main(){
    List l = new Node();
    int i = 0;
    List k = l;
    while (i < 10)
    {
        k->d = i;
        k->next = new Node();
        k = k->next; 
        i++;
    }
    List m = l;
    while ( m->next !=0 )
    {
        cout << m->d << endl;
        m = m->next;
    }
    reverse(l);
     m = l;
    while ( m->next !=0 )
    {
        cout << m->d << endl;
        m = m->next;
    }
}

Answer 1

This is not a typical way of iterating through a linked list:

while (m->next != 0) {
    cout << m->d << endl;
    m = m->next;
}

Instead, you should do:

while (m != 0) {
    cout << m->d << endl;
    m = m->next;
}

If you do this, you'll see that the linked list you initially created is actually:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0

Your Printing logic then prints it as:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Your reverse then likely functions correctly, producing a list of:

0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

Which you print as:

0, 9, 8, 7, 6, 5, 4, 3, 2, 1 

Answer 2

You wrongly initialized the list. The last node with d=9, it should have a null next, but it actually has a new Node. To fix that, change you list initialization to:

for (int i = 0; ; ++i)
{
    k->d = i;
    if (i >= 9) {
        break;
    }
    k->next = new Node();
    k = k->next; 
}

After changing that, you also need change your initial AND final printing(otherwise you won't print the last node). The print code should be(you'd better put it into a print function to avoid duplicate code):

for ( ; m; m = m->next)
{
    cout << m->d << endl;
}