Reversing a linked list-Find error in existing logic

Question

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode *p=NULL;
        ListNode *q=NULL;
        ListNode *r=NULL;
        r=head;
        q=head->next;
        if(q->next){
            p=q->next;
        }else{
            q->next=r;
            return q;
        }
        while(p){
            q->next=r;
            r=q;
            q=p;
            p=p->next;
        }
        head->next=NULL;
        return q;
    }
};

I know this is one of the most basic problems of linked list but I tried it on paper and then coded it but I am getting errors for don't know what reasons.Could somebody please point out the error in my logic and how to correct it?

P.s: Don't give me solutions rather help in finding errors in my code

Coding tip: ListNode *r=NULL; r=head; should be ListNode *r=head;. Don't waste time initializing an object with a value that you're going to immediately overwrite. — Pete Becker
– Pete Becker, Commented Jul 9, 2024 at 16:46
What do you mean by "getting errors"? Compiler errors? Runtime crashes? — Pete Becker
– Pete Becker, Commented Jul 9, 2024 at 16:51
Recommendation: Finish the example code off by adding the headers and a simple main function that feeds in an input that caused the problem you are asking about. — user4581301
– user4581301, Commented Jul 9, 2024 at 16:53
Side note: Read the tag info before using a tag for the first time (or the first time in a while). dsa, for example, is used with questions about the Digital Signature Algorithm, something noticeably absent from this question. — user4581301
– user4581301, Commented Jul 9, 2024 at 16:55
Recommendation: Help yourself visualize the problem by drawing pictures. Draw the list. Draw every step you need to perform to transform the list for the operation in question. Draw the final result. Then, with the help of a debugger, step through the code and doing exactly what the program does, attempt to redraw the pictures. If you can't, you'll easily see where your drawings and what the program does diverge and should have a pretty good idea what you need to do instead. — user4581301
– user4581301, Commented Jul 9, 2024 at 16:58

Aicody · Accepted Answer · 2024-07-09 17:06:01Z

The three-pointer method is correct. It just does not swap the nodes properly.

In the while loop,

ListNode *r = q->next;: saves the next node.
q->next = p;: reverses the current node's pointer.
p = q;: moves p to the current node.
q = r;: moves q to the next node (which is already saved in r)

Code

#include <iostream>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct Solution
{
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode *p = nullptr;
        ListNode *q = head;

        while (q)
        {
            ListNode *r = q->next;
            q->next = p;
            p = q;
            q = r;
        }

        return p;
    }
};

void display(ListNode *node)
{
    while (node != nullptr)
    {
        std::cout << node->val << "\t";
        node = node->next;
    }
    std::cout << "\n\n";
}

int main()
{
    ListNode *l = new ListNode(1);
    l->next = new ListNode(2);
    l->next->next = new ListNode(3);
    l->next->next->next = new ListNode(4);
    l->next->next->next->next = new ListNode(5);

    display(l);

    Solution solution;
    ListNode *rev = solution.reverseList(l);

    display(rev);

    while (rev)
    {
        ListNode *temp = rev;
        rev = rev->next;
        delete temp;
    }

    return 0;
}

Prints

1   2   3   4   5   

5   4   3   2   1

Collectives™ on Stack Overflow

Reversing a linked list-Find error in existing logic

1 Answer 1

Code

Prints

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Code

Prints

Comments

Your Answer

Sign up or log in

Post as a guest

Related