Is there something wrong with my reverse a linked list function ? It does not print the reversed linked list?

Question

#include "bits/stdc++.h"
using namespace std;
struct ListNode
{
    int val ;
    ListNode * next;
    ListNode( int c )
    {
        val = c;
        next = NULL;
    }
};
void traversal ( ListNode * head )
{
    ListNode*temp = head ;
    while ( temp != NULL)
    {
        cout << temp->val << " ";
        temp=temp->next;
    }
    cout<<endl;
}
ListNode* reverseList(ListNode* head) 
{
    ListNode * temp=head;
    ListNode *p=head; 
    ListNode *x=NULL ;
    while( head->val  != x-> val )
    {
        while( temp->next != x)
            temp=temp->next;
        
        swap(head->val,temp->next->val);
        x=temp->next;
        head=head->next;
        temp= head ;

    }
    return p;
}
int main()
{
    ListNode * head = new ListNode ( 10 );
    head->next = new ListNode ( 20 );
    head-> next -> next =new ListNode ( 30 );
    head-> next -> next-> next =new ListNode ( 40 );
    head-> next -> next-> next-> next =new ListNode ( 50 );
    traversal ( head ) ;
    head = reverseList ( head ) ;
    traversal ( head ) ;

    return 0 ;
}

OUTPUT:
10 20 30 40 50 The program ends after printing this. I'm trying to reverse a singly linked list. I know this is not the right algorithm, I'm just creating my own algo to reverse it.I'm trying to maintain 2 pointer to swap the last and the first element till we reach the middle where the head -> data == x-> data . I'm using x pointer to store the address of the nth node ( in this case say address of 50 ) so that the next time my list iterates till over the second last element.The problem is that my list is not getting printed when i call the function.

You immediatly and unconditionally dereference a NULL pointer here `ListNode *x=NULL ; while( head->val != x-> val )`. Fix that first before thinking any more about algos. — Yunnosch, Jun 29 '22 at 19:42
I suppose your algorithm is supposed to start at the head and tail and swap the values and then move inwards from both sides and repeat, right? So you have to set `x` to the tail instead of NULL. And if you are learning C++ then start using nullptr, not NULL. — Goswin von Brederlow, Jun 29 '22 at 19:55
One of the best tricks I know of to figure out linked lists is to draw a lot of pictures to help visualize the problem. You generally don't have to go this far, but if you draw the list and then each and every step as you transform the list, you'll see exactly what you need to do and you'll have a really good set of expectations to compare against when stepping through the program with a debugger to find mistakes. — user4581301, Jun 29 '22 at 20:00
Totally unrelated: The combination of `#include "bits/stdc++.h"` and `using namespace std;` can be disastrous. Best if you don't use either (read [this](https://stackoverflow.com/q/1452721/4581301) and [this](https://stackoverflow.com/q/31816095/4581301) for why), but using them together is practically inviting a boot to the head. — user4581301, Jun 29 '22 at 20:03
Thanks @GoswinvonBrederlow I worked on it and the code ran . — simple navi, Jun 29 '22 at 20:17
@user4581301 Yes I'm used to draw the list when I'm stuck ... thanks :) — simple navi, Jun 29 '22 at 20:19

Lajos Arpad · Answer 1 · 2022-06-29T20:06:38.223

1

Basically this is what you need to do:

ListNode* reverseList(ListNode* head)
{
    ListNode *current = head;
    ListNode *previous = NULL;
    while (current != NULL) {
        ListNode *next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    head = previous;
    return head;
}

Your while was looping with the condition of ( head->val != x-> val ), and temp is initialized with head, so the two values will always match and as a result, the while condition will never be true.

edited Jun 29 '22 at 20:06

answered Jun 29 '22 at 19:43

Lajos Arpad

64,414
37
100
175

The OP reverses the values of the list, not the linkage. That might be important if iterators are supposed to remain valid. – Goswin von Brederlow Jun 29 '22 at 19:54

score 0 · Answer 2 · answered Jun 29 '22 at 20:24

0

ListNode* reverseList(ListNode* head) 
{
    ListNode * temp=head, *p=head, *x=head;
    
    while ( x->next !=NULL)
        x=x->next;

    while( head->val  != x-> val )
    {
        while( temp->next != x)
        {
            temp=temp->next;
        }
        swap(head->val,temp->next->val);
        x=temp;
        head=head->next;
        temp= head ;
    }
    return p;
}

Fixed it :)

answered Jun 29 '22 at 20:24

simple navi

11

You swap out all the values in the list without changing the structure of the list. So you can use `void reverseList(ListNode* head)`. The `head` pointer remains valid after reversal. Note: Swapping the values might be expensive it the list holds something other than `int`. Reversing the `next` pointers is the more common solution. The function prototype used indicates that was the desired algorithm. – Goswin von Brederlow Jun 29 '22 at 20:43
I was trying to reverse the singly linked list on my own before learning the right algorithm. I now know the most efficient approach is to reverse by reversing the next pointers as u said ... thanks:) – simple navi Jun 30 '22 at 11:39

Is there something wrong with my reverse a linked list function ? It does not print the reversed linked list?

2 Answers2