Reversing a Linked List not working in C. Only giving the top element-CodePudding

I tried reversing a linked list using the following code but only the first element of the unreversed linked list is been shown in the print.

Please help.

The output is:

Element: 7
Element: 11
Element: 66
------------------
Element: 7

The elements before dashes are unreversed and below are reversed with is not happenning.

#include <iostream>
using namespace std;

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

void LinkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

struct Node *Reverse(struct Node *head)
{
    Node *cur = head;
    Node *prev = NULL;
    Node *temp;
    // temp;
    while (cur != NULL)
    {
        /* code */
        temp = cur->next;
        cur->next = prev;
        prev= cur;
        // cout<<prev->next<<endl;
        cur = temp;

    }
    head =  prev;
    return head;
}

int main()
{

    // Creation of Linked List
    struct Node *head;
    struct Node *second;
    struct Node *third;

    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    head->data = 7;
    head->next = second;

    second->data = 11;
    second->next = third;

    third->data = 66;
    third->next = NULL;

    LinkedListTraversal(head);
    Reverse(head);
    cout << "------------------\n";
    LinkedListTraversal(head);

    return 0;
}

CodePudding user response：

Your Reverse function works perfectly well.

Your will laugh, because your mistake is really silly : you use the wrong parameter for your function. Now that your list is reversed, head is the new tail and it points to NULL.

Call your function like that :

LinkedListTraversal(head);
Reverse(head);
cout << "------------------\n";
LinkedListTraversal(third);

CodePudding user response：

You have a list like 7 -> 11 -> 66 where head points to 7. Then you reverse the list to 66 -> 11 -> 7. The new head should point to 66. Your code prints the list from the unmodified head which still points to 7.

Your function Reverse is designed to return the new list head, but you ignore the return value. Use

head = Reverse(head);

to get the new head in your main function.

Maybe you thought that Reverse would modify the head value in main. This is not true. The function modifies a local copy of the pointer only. That's why it returns the new value. If you would design Reverse to take the address of the head pointer, it could modify the pointer in main.

Alternative solution:

/* modified lines marked with comments ***** */
struct Node *Reverse(struct Node **head)
{
    Node *cur = *head;  /*****/
    Node *prev = NULL;
    Node *temp;
    // temp;
    while (cur != NULL)
    {
        /* code */
        temp = cur->next;
        cur->next = prev;
        prev= cur;
        // cout<<prev->next<<endl;
        cur = temp;

    }
    *head =  prev; /*****/
}


/* and to pass the address of the head pointer, call it like */
Reverse(&head);