Reverse each word in the linked list node

A linked list is a linear data structure similar to a chain, in which elements are not stored in memory in an adjacent manner like an array. In a specific linked list, an element is connected to the next element through a pointer. Simply put, a linked list is a series of data containers where we can find a path or reference link to the next node. In a linked list, there is a head pointer as the first element. If the first node of that particular linked list is empty, then it points to nothing or is empty.

There are different types of linked lists in the data structure.

• Singly Linked list − It is a basic type of linked list present in data structure, where every node contains some data with a pointer of the same data type for the next node. Here for this linked list both the time complexity and auxiliary space is O(n).

• Doubly linked list − It is a complex doubly linked list that contains a pointer as a sequence of previous nodes. This type of linked list contains three different parts: the data source, the pointer, and the next node. With this linked list, we can traverse the entire list in reverse order.

• Circular Linked List − In a circular linked list the first node pointer indicated by the last node of the list. It means, the list has no start and no ending point. To traverse a circular linked list, the user can start from any node and traverse the list in forward or backward direction as their wish.

• Two-way circular linked list - This is a two-way circular linked list, which contains pointers to the previous node and the next node. The previous node of its first node does not contain a null value.

In this article, we will build some code for the linked list mentioned above, and through these codes, we will learn how to reverse each word in the linked list node in a C environment.

Algorithm to reverse each word present in a linked list node

• Step one - declare a temporary array.

• Step 2 − Traverse a linked list.

• Step 3 − If the current element is an alphabet then store the element.

• Step 4 − Else, increase node by 1 pointer.

• Step 5 - Traverse from the head again.

• Step 6 − If the current element is alphabet then copy it to the last element.

• Step 7 - Reduce the current index.

• Step 8 - Iteration is necessary.

• Step 9 - Otherwise, increase it by one.

Syntax for reversing each word in a linked list node

insertEnd(head, new_node)
Declare last
   if head == NULL then
      new_node->next = new_node->prev = new_node
      head = new_node
      return
   last = head->prev
   new_node->next = head
   head->prev = new_node
   new_node->prev = last
   last->next = new_node
reverse(head)
   Initialize new_head = NULL
   Declare last
   last = head->prev
   Initialize curr = last, prev
   while curr->prev != last
      prev = curr->prev
      insertEnd(&new_head, curr)
      curr = prev
   insertEnd(&new_head, curr)
return new_head

Following method:

• Approach 1 − Reverse each word present in a linked list

• Approach 2 − Reverse the whole sentence present in a linked list.

• Approach 3 − Reverse a doubly circular linked list.

• Approach 4 − Reverse a circular linked list.

• Path 5 − Reverse the linked list without affecting special characters.

Reverse each word present in a linked list by using C

Here in this particular C build code we have reversed each word present in a linked list.

The Chinese translation of

Example 1

is:

Example 1

#include <bits/stdc++.h>
using namespace std;
struct Node {
   string c;
   struct Node* next;
};
struct Node* newNode(string c){
   Node* temp = new Node;
   temp->c = c;
   temp->next = NULL;
   return temp;
};
void reverse_word(string& str){
   reverse(str.begin(), str.end());
}
void reverse(struct Node* head){
   struct Node* ptr = head;
   while (ptr != NULL) {
      reverse_word(ptr->c);
      ptr = ptr->next;
   }
}
void printList(struct Node* head){
   while (head != NULL) {
      cout << head->c << " ";
      head = head->next;
   }
}
int main(){
   Node* head = newNode("Train number 13109");
   head->next = newNode("Maitree Express");
   head->next->next = newNode("is an international train");
   head->next->next->next = newNode("runs between");
   head->next->next->next->next = newNode("Kolkata");
   head->next->next->next->next->next = newNode("and");
   head->next->next->next->next->next->next = newNode("Dhaka");
   cout << "The list here present before reverse: \n";
   printList(head);
   reverse(head);
   cout << "\n\nList after reverse we can see like: \n";
   printList(head);
   return 0;
}

Output

The list here present before reverse: 
Train number 13109 Maitree Express is an international train runs between Kolkata and Dhaka 

List after reverse we can see like: 
90131 rebmun niarT sserpxE eertiaM niart lanoitanretni na si neewteb snur atakloK dna akahD 

Reverse the entire sentence in the linked list

In this particular code, we have reversed the entire sentence in the linked list.

#include <bits/stdc++.h>
using namespace std;
string reverseString(string str){
   reverse(str.begin(), str.end());
   str.insert(str.end(), ' ');
   int n = str.length();
   int j = 0;
      for (int i = 0; i < n; i++) {
      if (str[i] == ' ') {
         reverse(str.begin() + j,
         str.begin() + i);
         j = i + 1;
      }
   }
   str.pop_back();
   return str;
}
int main(){
   string str = "13110, Maitree Express Is An International Train Runs Between Dhaka And Kolkata";
   string rev = reverseString(str);
   cout << rev;
   return 0;
}

Output

Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,

Reverse a doubly circular linked list

Here in this particular code we have reversed a doubly circular linked list.

The Chinese translation of

Example 3

is:

Example 3

#include <bits/stdc++.h><bits stdc++.h="">
using namespace std;
struct Node {
   int data;
   Node *next, *prev;
};
Node* getNode(int data){
   Node* newNode = (Node*)malloc(sizeof(Node));
   newNode->data = data;
   return newNode;
}
void insertEnd(Node** head, Node* new_node) {
   if (*head == NULL) {
      new_node->next = new_node->prev = new_node;
      *head = new_node;
      return;
   }
   Node* last = (*head)->prev;
   new_node->next = *head;
   (*head)->prev = new_node;
   new_node->prev = last;
   last->next = new_node;
}
Node* reverse(Node* head) {
   if (!head)
   return NULL;
   Node* new_head = NULL;
   Node* last = head->prev;
   Node *curr = last, *prev;
   while (curr->prev != last) {
      prev = curr->prev;
      insertEnd(&new_head, curr);
      curr = prev;
   }
   insertEnd(&new_head, curr);
   return new_head;
}
void display(Node* head){
   if (!head)
   return;
   Node* temp = head;
   cout << "Forward direction data source: ";
   while (temp->next != head) {
      cout << temp->data << " ";
      temp = temp->next;
   }
   cout << temp->data;
   Node* last = head->prev;
   temp = last;
   cout << "\nBackward direction data source: ";
   while (temp->prev != last) {
      cout << temp->data << " ";
      temp = temp->prev;
   }
   cout << temp->data;
}
int main(){
   Node* head = NULL;
   insertEnd(&head, getNode(16));
   insertEnd(&head, getNode(10));
   insertEnd(&head, getNode(07));
   insertEnd(&head, getNode(2001));
   insertEnd(&head, getNode(1997));
   cout << "Current list here present:\n";
   display(head);
   head = reverse(head);
   cout << "\n\nReversed list here present:\n";
   display(head);
   return 0;
}
</bits>

Output

Current list here present:
Forward direction data source: 16 10 7 2001 1997
Backward direction data source: 1997 2001 7 10 16

Reversed list here present:
Forward direction data source: 1997 2001 7 10 16
Backward direction data source: 16 10 7 2001 1997

Reverse circular linked list

In this particular code, we have reversed a circular linked list data set.

The Chinese translation of

Example 4

is:

Example 4

#include <bits/stdc++.h><bits stdc++.h="">
using namespace std;
struct Node {
   int data;
   Node* next;
};
Node* getNode(int data){
   Node* newNode = new Node;
   newNode->data = data;
   newNode->next = NULL;
   return newNode;
}
void reverse(Node** head_ref){
   if (*head_ref == NULL)
   return;
   Node* prev = NULL;
   Node* current = *head_ref;
   Node* next;
   do {
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
   } while (current != (*head_ref));
   (*head_ref)->next = prev;
   *head_ref = prev;
}
void printList(Node* head){
   if (head == NULL)
   return;
   Node* temp = head;
   do {
      cout << temp->data << " ";
      temp = temp->next;
   } while (temp != head);
}
int main(){
   Node* head = getNode(10);
   head->next = getNode(16);
   head->next->next = getNode(07);
   head->next->next->next = getNode(2022);
   head->next->next->next->next = head;
   cout << "Given circular linked list is here: ";
   printList(head);
   reverse(&head);
   cout << "\nReversed circular linked list after method: ";
   printList(head);
   return 0;
}
</bits>

Output

Given circular linked list is here: 10 16 7 2022 
Reversed circular linked list after method: 2022 7 16 10 

Reverse a linked list without affecting special characters

Here in this particular code we have reversed the data set of linked list without affecting special characters.

Example 5

#include <iostream>
using namespace std;
struct Node {
   char data;
   struct Node* next;
};
void reverse(struct Node** head_ref, int size){
   struct Node* current = *head_ref;
   char TEMP_ARR[size];
   int i = 0;
   while (current != NULL) {
      if ((current->data >= 97 && current->data <= 122) ||
      (current->data >= 65 && current->data <= 90)) {
         TEMP_ARR[i++] = current->data;
         current = current->next;
      }
      else
      current = current->next;
   }
   current = *head_ref;
   while (current != NULL) {
      if ((current->data >= 97 && current->data <= 122) ||
      (current->data >= 65 && current->data <= 90)) {
         current->data = TEMP_ARR[--i];
         current = current->next;
      }
      else
      current = current->next;
   }
}
void push(struct Node** head_ref, char new_data){
   struct Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(struct Node* head){
   struct Node* temp = head;
   while (temp != NULL) {
      cout << temp->data;
      temp = temp->next;
   }
}
// Driver program to test above function
int main() {
   struct Node* head = NULL;
   push(&head, 'R');
   push(&head, 'U');
   push(&head, 'D');
   push(&head, 'R');
   push(&head, 'A');
   push(&head, 'K');
   push(&head, 'O');
   push(&head, 'L');
   push(&head, 'K');
   push(&head, 'A');
   push(&head, 'T');
   push(&head, 'A');
   push(&head, '0');
   push(&head, '1');
   push(&head, '0');
   push(&head, '@');
   cout << "Given linked list is here: ";
   printList(head);
   reverse(&head, 13);
   cout << "\nReversed Linked list is here: ";
   printList(head);
   return 0;
}

Output

Given linked list is here: B@010ATAKLOKARDUR
Reversed Linked list is here: R@010UDRAKOLKATAB

Conclusion

In this article, we learned how to reverse each word in a linked list node. We have constructed the C code here to show the possible reversal process so that you can get a broad understanding of the reversal of linked list nodes.

The above is the detailed content of Reverse each word in the linked list node. For more information, please follow other related articles on the PHP Chinese website!