Convert A String To A Singly Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we will be given a string, and we need to convert it into a singly linked list where each node will contain a single character.

Problem Statement Understanding

Let’s try to understand this problem with the help of examples.

If the string given to us is “leaf”:

  • Then, according to the problem statement, we have to convert this string to a singly linked list.
  • The output linked list after converting the given string “leaf” to a singly linked list will be: l→e→a→f→NULL.
  • While converting the string to a singly linked list, each character in the input string will be treated as a single node of our newly created linked list.

Let’s take another example, say if the Input string: “prepbytes”

  • In this case, our output singly linked list will be: p→r→e→p→b→y→t→e→s→NULL

Now, I think the problem statement is clear, so let's see how we can approach it. Any ideas? If not, it's okay. We will see in the next section how we can approach it.

Approach

  • As the nodes of our output singly linked list will be having character in data field, so we will make our node class having a char variable that will store character data and a next pointer to store the next node’s address.
  • Loop through the string and create the nodes while iterating through it.
  • Make the last node’s next pointer NULL.

Algorithm :

1) Check if the string is empty.

  • If it is empty, return a NULL pointer.
  • Else, proceed ahead.
    2) Create a node that will store the first character of our string, and it will be the head of our newly created list.
    3) Initialize a curr pointer with the above-created node.
    4) Start iterating the string from its second character till last
  • Create a new node and assign curr→next to it.
  • Update the curr pointer to the newly created node.
    5) Return the head pointer

Now, we will get our desired list as output, and we could print it to check.

Dry Run


Code Implementation

#include 
using namespace std;

// class with constructor for a Singly Linked List
class node {
    public:
    char data;
    node* next;
    // constructor
    node(char x){
        data = x;
        next = NULL;
}
};

// This function converts a string to a singly linked list
node* string_to_SLL(string s)
{
    // check if the string is empty 
    if(s.size() == 0) return NULL;
    // create a head pointer as discussed in step 2
    node *head = new node(s[0]);
    // create a pointer to store the address of previously created node
    node* curr = head;

    // iterate from second character to the last character
    for (int i = 1; i < s.size(); i++) {
        // create a new node and attach it to previously created node
        curr->next = new node(s[i]);
        // update the curr pointer to newly created node
        curr = curr->next;
    }
    return head;
}

// This function is used to print the content of linked list
void print(node* head)
{
    node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL";
}

// main function
int main()
{
    string s = "leaf";
    node *head = string_to_SLL(s);
    print(head);
    return 0;
}

Output

l→e→a→f→NULL

Time complexity: O(n), Where n is the number of characters in the string.
Space Complexity: O(n), as we are creating a singly linked list having n nodes.

So, in this blog, we have tried to explain how you can convert a string to a singly linked list in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.ode.prepbytes.com/interview-coding/practice/linked-list).

Previous post C program for performing Bubble sort on Linked List
Next post Implementation of Deque Using Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *