Reversing Linked List - C++

Question

I wrote a function that should reverse a list.

So far, I can reverse only two items, but no more. I checked and double checked and still can't find the problem. I even used the Debugger to see the value of each pointer. When running the debugger, I received the message:

An access violation (segmentation fault) raised in your program.

This is my first assignment with linked lists so I am still learning.

Here is the code I wrote in Dev-C++:

List::ListNode *List::Reverse_List(ListNode *head)
{
    ListNode *cur = head;
    ListNode *forward = NULL;
    ListNode *previous = NULL;

    while (cur != NULL)
    {
        head = cur; //set the head to last node
        forward = head->next;  //save the next pointer in forward
        cur->next = previous;  //change next to previous
        previous = cur;
        cur = forward;

        cout << "cur= " << cur->item << endl; //this is just to display the current value of cur

        return head;
    }
}

What is the final node the member function returns? How are you making the reversed list head node previous element to NULL ? — Mahesh, Oct 26 '11 at 00:12
oups! my bad, i forgot to return *head; I will edit the code. Thanks. — T4000, Oct 26 '11 at 00:17
But the program stops working. I still can't figure out the problem. — T4000, Oct 26 '11 at 00:23
Besides, after compiling the source, i also get the message :"[Linked error] undefined reference to 'WinMain@16' ID returned 1 exit status. I still can't find the causes of that message. — T4000, Oct 26 '11 at 00:27
Take the `return head;` out of the loop, it'll return after one iteration. Show us the declaration of a `ListNode`, if each node stores a next and a previous pointer then it'll be fairly simple. — AusCBloke, Oct 26 '11 at 00:49
possible duplicate of [Create a reverse LinkedList in C++ from a given LinkedList](http://stackoverflow.com/questions/4908193/create-a-reverse-linkedlist-in-c-from-a-given-linkedlist) — Xeo, Oct 26 '11 at 02:03
Aside from the duplicate, your code seems correct if you move the return out of the loop. Double-check with my answer provided in the link if you're still unsure. — Xeo, Oct 26 '11 at 02:05
The linker error has nothing to do with the code you posted. When building a Win32 application, instead of a function called main, you need to have a function called WinMain. — IronMensan, Oct 26 '11 at 02:27

score 4 · Answer 1 · answered Oct 26 '11 at 02:03

4

Your code is close, it is returning early.

List::ListNode *List::Reverse_List(ListNode *head) 
{
    ListNode *cur = head;
    ListNode *forward = NULL;
    ListNode *previous = NULL;

    while (cur != NULL) {
        //There is no need to use head here, cur will suffice
        //head = cur; //set the head to last node
        forward = cur->next; //save the next pointer in forward

        cur->next = previous; //change next to previous
        previous = cur;
        cur = forward;

        cout << "cur= " << cur->item << endl; //this is just to display the current value of cur

        //don't return here you have only adjusted one node
        //return head;
    }

    //at this point cur is NULL, but previous still holds the correct node
    return previous;
}

answered Oct 26 '11 at 02:03

IronMensan

6,761
1
26
35

even when i use the code above, I still have the same issue: I cannot obtain a reverse list with more than 2 items. And the program stops spontaneously. I am still trying to figure out, but, nothing comes out. – T4000 Oct 26 '11 at 02:20
I suspect that the program stops running because I have a this error [linker error] undefined reference to WinMain@16 Id returned 1 exit status. On this one too, i still cannot figure out the problem. – T4000 Oct 26 '11 at 02:23
2

If you are getting linker errors, then you are not actually running the code you changed, you are running whatever was built the last time you had a successful build. – IronMensan Oct 26 '11 at 02:29

score 0 · Answer 2 · answered Oct 22 '13 at 23:39

Sorry for answering late and I am sure that you would have found the answer by now but yet it might be helpful for others. Answer is simply taking return statement (i.e. return head;) out of while loop will fix your problem. Though there are ways you can avoid extra pointer and assignments to optimise your code.

score 0 · Answer 3 · answered Oct 26 '11 at 21:28

Everyone must have the same homework assignment today.

I think it would be more helpful to these people to show them what happens to the state of the list while it is being reversed. This should help them better than showing them code or code problems.

Here is what should happen (with the algorithm I would use)

[] = head () = current

([1])->2->3->4, [2]->(1)->3->4, [3]->2->(1)->4, [4]->3->2->(1) done because current now doesn't have a new next

Reversing Linked List - C++

3 Answers3