数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学反转链表节点中的每个单词
链表是一种类似链状的线性数据结构，与数组不同，其元素并非连续存储在内存中。在特定的链表中，元素通过指针与下一个元素链接。简单来说，链表是一系列数据容器，这些容器中的元素包含指向下一个节点的路径或引用链接。链表的第一个元素是一个头指针。如果该列表的第一个节点为空，则它不指向任何内容或为空。
数据结构中存在不同类型的链表。
单链表 − 它是数据结构中一种基本的链表类型，每个节点都包含一些数据以及指向下一个节点的相同数据类型的指针。对于此链表，时间复杂度和辅助空间都是 O(n)。
双链表 − 这是一种复杂的双向链表，包含一个指向前一个节点的序列指针。这种类型的链表包含三个不同的数据源部分：数据、指针和下一个节点。通过它，我们可以反向遍历整个列表。
循环链表 − 在循环链表中，第一个节点指针由列表的最后一个节点指示。这意味着列表没有起点也没有终点。要遍历循环链表，用户可以从任何节点开始，并根据需要向前或向后遍历列表。
双向循环链表 − 这是一种双向循环链表，包含指向前一个节点和下一个节点的指针。它不包含指向第一个节点之前的空值。
在本文中，我们将为上述链表构建一些代码，通过这些代码，我们将学习如何在 C++ 环境中反转链表节点中的每个单词。
反转链表节点中每个单词的算法
步骤 1 − 声明一个临时数组。
步骤 2 − 遍历链表。
步骤 3 − 如果当前元素是字母，则存储该元素。
步骤 4 − 否则，将节点指针加 1。
步骤 5 − 从头节点再次遍历。
步骤 6 − 如果当前元素是字母，则将其复制到最后一个元素。
步骤 7 − 减少当前索引。
步骤 8 − 需要进行迭代。
步骤 9 − 否则，将其加 1。
反转链表节点中每个单词的语法
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
遵循的方法：-
方法 1 − 反转链表中的每个单词
方法 2 − 反转链表中的整个句子。
方法 3 − 反转双向循环链表。
方法 4 − 反转循环链表。
方法 5 − 反转链表而不影响特殊字符。
使用 C++ 反转链表中每个单词
在此特定的 C++ 代码中，我们反转了链表中存在的每个单词。
示例 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;
}
输出
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;
}
输出
Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,
反转双向循环链表
在此特定代码中，我们反转了一个双向循环链表。
示例 3
#include <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; }
输出
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
反转循环链表
在此特定代码中，我们反转了循环链表的数据集。
示例 4
#include <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; }
输出
Given circular linked list is here: 10 16 7 2022 Reversed circular linked list after method: 2022 7 16 10
反转链表而不影响特殊字符
在此特定代码中，我们反转了链表的数据集，而不影响特殊字符。
示例 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;
}
输出
Given linked list is here: B@010ATAKLOKARDUR Reversed Linked list is here: R@010UDRAKOLKATAB
结论
在今天的文章中，我们学习了如何反转链表节点中存在的每个单词。我们在此构建了 C++ 代码以及可能的方法，以向您全面介绍链表节点可能的反转过程。
更新于：2023年4月5日
259 次浏览
广告