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

Answer 1

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