链表是一种类似链式的线性数据结构，其中元素不像数组那样按相邻的方式保存在内存中。在特定的链表中，元素通过指针与下一个元素相连。简单来说，链表是一系列数据容器，我们可以在这些元素中找到一条路径或引用链接到下一个节点。在链表中，有一个头指针作为第一个元素。如果该特定链表的第一个节点为空，则它不指向任何内容或为空。
在数据结构中存在不同类型的链表。
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).
双向链表 − 它是一个复杂的双向链表，其中包含一个指针作为前一个节点的序列。这种类型的链表包含三个不同的部分：数据源、指针和下一个节点。通过这种链表，我们可以以反向的方式遍历整个列表。
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.
双向循环链表 - 这是一个双向循环链表，它包含了前一个节点和后一个节点的指针。它的第一个节点的前一个节点不包含空值。
在本文中，我们将为上述提到的链表构建一些代码，通过这些代码，我们将学习如何在C++环境中反转链表节点中的每个单词。
Algorithm to reverse each word present in a linked list node
第一步 - 声明一个临时数组。
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 6 − If the current element is alphabet then copy it to the last element.
步骤 7 - 减少当前索引。
第8步 - 必须进行迭代。
第9步 - 否则，将其增加一。
将链表节点中的每个单词反转的语法
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
跟随的方法：
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.
途径5 − 在不影响特殊字符的情况下反转链表。
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.
Example 1
的中文翻译为：示例 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
反转链表中的整个句子
在这个特定的代码中，我们已经将链表中的整个句子进行了反转。
#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.
Example 3
的中文翻译为：示例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
反转循环链表
在这个特定的代码中，我们已经反转了一个循环链表的数据集。
Example 4
的中文翻译为：示例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
反转一个链表而不影响特殊字符
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
在本文中，我们学习了如何反转链表节点中的每个单词。我们在这里构建了C++代码，以展示可能的反转过程，以便您对链表节点的反转有一个广泛的了解。
