C Linked List Reverse Function Triggers Infinite Loop-CodePudding

I've created a linked list from an array. It works fine. But when I try to reverse the list using the reverseList() function, it starts an infinite loop. When I try to display the list, it displays the last two members repeatedly.

#include <bits/stdc  .h>
using namespace std;

struct node
{
    int data;
    struct node *next;
};

node *reverseList(node *h)
{
    node *p, *q, *r;
    p = h->next;
    q = h;
    r = NULL;
    while (p)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    h = q;
    return h;
}

int main()
{
    struct node *n, *h, *t;
    int arr[] = {2, 5, 9, 6, 8};
    n = new node;
    t = n;
    h = n;
    n->data = arr[0];

    for (int i = 1; i < 5; i  )
    {
        n = new node;
        n->data = arr[i];
        t->next = n;
        t = n;
    }
    n->next = NULL;
    node *p = reverseList(h);
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }

    return 0;
}

CodePudding user response：

Within the function reverseList

node *reverseList(node *h)
{
    node *p, *q, *r;
    p = h->next;
    q = h;
    r = NULL;
    while (p)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    h = q;
    return h;
}

initially q->next for the first node pointed to by the pointer h is not set to nullptr. It stays pointing to the second node in the original list.

That is after this statement

q = h;

before the while loop the pointer q->next was not set to nullptr.

Also the function can invoke undefined behavior if the passed argument is a null pointer.

The function can be defined the following way

node * reverseList( node *h )
{
    node *q = nullptr;

    for ( node *p = h; h != nullptr; p = h )
    {
        h = h->next;
        p->next = q;
        q = p;
    }

    h = q;

    return h;
}

Or it would be better to use more meaningful names like for example

node * reverseList( node *head )
{
    node *new_head = nullptr;

    for ( node *current = head; head != nullptr; current = head )
    {
        head = head->next;
        current->next = new_head;
        new_head = current;
    }

    return new_head;
}

Pay attention to that you need to free all the allocated memory for the list when it is not required any more.