reverse a string using singly linked list

Question

i am trying to print the reverse of the string using linked list. suppose my string is "World is full of good people" , it should print "people good of full is World"

#include <iostream>

using namespace std;
/******** Fucntions Prototype *********/

void printList();


typedef struct Node
{
    string data;
    struct Node *next;
}node;

struct Node* newNode(string userData)
{
    node *temp = new Node;
    temp->data = userData;
    temp->next = NULL;
    return temp;
}

void printList(node* head)
{
    node *temp = head;
    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
void reverseList(node *head)
{
    node *curr = head;
    node *prev = NULL, *next = NULL;
    while(curr != NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;

}
int main()
{
    node *head = newNode("World");
    head->next = newNode("is");
    head->next->next = newNode("full");
    head->next->next->next = newNode("of");
    head->next->next->next->next = newNode("good");
    head->next->next->next->next->next = newNode("people");
    cout<<"Linked list before reverse is:\n";
    printList(head);
    cout<<"\n";
    reverseList(head);
    cout<<"Linked list after reverse is:\n";
    printList(head);

    return 0;
}

So if the string is "World is full of good people", the expected output is "people good of full is world", hence reversing the node. But is getting "World" as output

Can you tell us why you have inserted element in linked list in this manner? Don't you think use of loop here? — iamrajshah, May 07 '19 at 08:45
If the only problem is to get "world" (lower case) instead of "World", this has nothing to do with reversing the list. The question is: Should the data in the list node get changed to lower case or do you want lower case only in the output? If you want the data to be modified: Should the case get changed in `reverseList()` or would you prefer a separate function, e.g `lowercasseList()`? — Bodo, May 07 '19 at 08:47
@Bodo, may be that is typo error, my intention is to reverse the list, the same logic i tried with Interger array, but with string i am getting this issue. The output i am getting some thing like this: Linked list before reverse is: World is full of good people Linked list after reverse is: World — sushant, May 07 '19 at 08:55
@sushant If you store the string "Word" (with an uppercase 'W') in a node of your list, why would you expect that reversing the list would change it to "world" (all lowercase)? If you need this, you would have to add code that modifies the data somewhere. This is not related to a typo or bug in your code. You simply didn't add code that implements the requested change. — Bodo, May 07 '19 at 08:58
@Bodo, let me put it clear, If entered string is "how are you" and expected output should be "you are how", no lowercase/uppercase, ignore the typo error in description of this thread. — sushant, May 07 '19 at 09:01
@sushant If you have a typo in your question, please [edit] the question and remove the typo to make it clear. So the problem is that the other words are missing in the output? Did you check the list after `reverseList()` using a debugger? — Bodo, May 07 '19 at 09:08

score 3 · Accepted Answer · answered May 07 '19 at 09:19

So reversing the list is not the problem, See that you passed the head by value So you're essentially making changes to the copy of head. Please have a look at pass by value vs pass by reference for more information on this.

The solution to your problem is to change your prototype to void reverseList(node **head) and each subsequent access of head will have to deferencened using *head.

Lastly, call your function with reverseList(&head);

score 1 · Answer 2 · answered May 07 '19 at 09:27

1

void reverseList(node *head) -- Here you are updating the temporary head which is passed by value.

Change the function declaration to void reverseList(node*& head)

answered May 07 '19 at 09:27

Wander3r

1,801
17
27

reverse a string using singly linked list

2 Answers2