链表是一种类似链式的线性数据结构，其中元素不像数组那样按相邻的方式保存在内存中。在特定的链表中，元素通过指针与下一个元素相连。简单来说，链表是一系列数据容器，我们可以在这些元素中找到一条路径或引用链接到下一个节点。在链表中，有一个头指针作为第一个元素。如果该特定链表的第一个节点为空，则它不指向任何内容或为空。
在数据结构中存在不同类型的链表。
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
#includeusing 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
反转链表中的整个句子
在这个特定的代码中，我们已经将链表中的整个句子进行了反转。
#includeusing 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
#includeusing 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; }
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
#includeusing 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; }
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
#includeusing 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++代码，以展示可能的反转过程，以便您对链表节点的反转有一个广泛的了解。
