-2

This code is supposed to reverse a linked list. The following code returns an empty linked list even when provided with a non empty list.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* curr, *prev, *next;
        if (head == NULL)
        {
            return head;   
        }   
        curr = head;
        prev = NULL;
        while (curr != NULL)
        {
            next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        return head;
    }
};

While this code strangely works where I added a cout statement just to check if the else was triggered.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* curr, *prev, *next;
        if (head == NULL)
        {
            cout << "Triggered";
            return head;   
        }   
        curr = head;
        prev = NULL;
        while (curr != NULL)
        {
            next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        return head;
    }
};

Can someone please explain why this is happening?

Paawan Angra
  • 75
  • 4
  • 4
    You never initialize `next`, so the first iteration of the while loop is Undefined Behavior. – 1201ProgramAlarm Jun 20 '20 at 16:37
  • 1
    I wrote an answer that might help you learn to figure it out. https://stackoverflow.com/questions/59545328/not-understanding-linked-list-implementation-please-help-c/59549084#59549084 – Ingo Mi Jun 20 '20 at 16:40
  • 2
    You may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Andreas Wenzel Jun 20 '20 at 16:44

2 Answers2

1

Pretty simple, you have to initialize the pointers, else it leads to unexpected behavior that includes not showing it at all or just showing it if an initialized cout is triggered - but it doesn't have to do anything and that's up to your compiler implementation.

//cpp17
    listNode* curr{}, *prev{}, *next{};

//before
    listNode* curr = nullptr, *prev = nullptr, *next = nullptr;

It is still not in the reverse order as you intended to do.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        listNode* curr{}, *prev{}, *next{};
        //ListNode* curr, *prev, *next;
        if (head == NULL)
        {
            return head;   
        }   
        curr = head;
        prev = NULL;
        while (next != NULL)
        {
            next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        return head;
    }
};

cheers :)

Ingo Mi
  • 999
  • 12
  • 26
  • Hey, thanks for the advice. Found the issue with the code too, I was just being super stupid. :D – Paawan Angra Jun 20 '20 at 19:42
  • @PaawanAngra Au nice, you're welcome bud :) Feel free to check the "solved" marker for the answer (under the voting button) I actually felt the urge to solve your problem myself (reverse the linked list) maybe tonight I find time for that. If you solved your reversing problem feel free to edit your question with the proper code (just keep the error) and in general your down votes get changed to upvotes and also add the main function to get a minimal full executable example to reproduce your problem just by copy and paste without the hustle to write the missing clutter around your Q – Ingo Mi Jun 20 '20 at 20:16
0

Like mentioned before I found time to write a solution for an other approach of solving your problem to reverse a linked list via class. For a better understanding for beginners I skipped the rule of three/five and initialized the list in the main function and not via constructor in the class:

#include <iostream>

class listElement
{
    std::string data;
    listElement* next;
    listElement* last;


public:
    void setData(std::string);
    void append(std::string);
    void displayElements();
    void reverseDisplayElements(listElement*);
    void freeMemory();

    listElement* reverseList(listElement*);
};

void listElement::setData(std::string newData)
{
    last = this;
    data = newData;
    next = nullptr;
}

void listElement::append(std::string newData)
{
// Double linked list
//    last->next = new listElement();
//    last->next->data = newData;
//    last->next->next = nullptr;
//    last = last->next;

// Singly linked list
    //has next the value nullptr?
    //If yes, next pointer
    if (next == nullptr)
    {
        next = new listElement();
        next->data = newData;
        next->next = nullptr;
    }
    //else the method again
    else
        next->append(newData);
}

listElement* listElement::reverseList(listElement* head)
{
    //return if no element in list
    if(head == nullptr)
        return nullptr;

    //initialize temp
    listElement* temp{};

    while(head != nullptr){
        listElement* next = head->next;
        head->next = temp;
        temp = head;
        head = next;
    }
    return temp;
}

void listElement::displayElements()
{
    //cout the first entry
    std::cout << data << std::endl;
    //if the end is not reached, call method next again
    if (next != nullptr)
        next->displayElements();
}

void listElement::reverseDisplayElements(listElement*head)
{
    //recursiv from the last to the list beginning - stop
    listElement *temp = head;

    if(temp != nullptr)
    {
        if(temp->next != nullptr)
        {
            reverseDisplayElements(temp->next);
        }
      std::cout << temp->data << std::endl;
    }
}
void listElement::freeMemory()
{
    //If the end is not reached, call the method again
    if (next != nullptr)
    {
        next->freeMemory();
        delete(next);
    }
}

int main ()
{
    //Pointer to the Beginning of the list
    listElement* linkedList;

    //Creating the first element
    linkedList = new listElement();
    //Write data in the first element
    linkedList->setData("Element 1");

    //add more elements
    linkedList->append("Element 2");
    linkedList->append("Element 3");
    linkedList->append("Element 4");

    //display list
    linkedList->displayElements();

    //space divider
    std::cout << "\nPrint in reverse order:" << std::endl;

    //display list in reverse order
    //pass list beginning as stop point
    linkedList->reverseDisplayElements(linkedList);
    std::cout << std::endl;

    linkedList->displayElements();
    std::cout << "\nReverse elements:" << std::endl;

    linkedList = linkedList->reverseList(linkedList);
    linkedList->displayElements();

    std::cout << std::endl;

    //destruct the list and free memory
    linkedList->freeMemory();
    delete(linkedList);

    return 0;
}

Btw. there are many different solutions for that task.

Ingo Mi
  • 999
  • 12
  • 26