首页  >  文章  >  后端开发  >  将链表节点中的每个单词反转

将链表节点中的每个单词反转

王林
王林转载
2023-09-01 10:25:03919浏览

将链表节点中的每个单词反转

链表是一种类似链式的线性数据结构,其中元素不像数组那样按相邻的方式保存在内存中。在特定的链表中,元素通过指针与下一个元素相连。简单来说,链表是一系列数据容器,我们可以在这些元素中找到一条路径或引用链接到下一个节点。在链表中,有一个头指针作为第一个元素。如果该特定链表的第一个节点为空,则它不指向任何内容或为空。

在数据结构中存在不同类型的链表。

  • 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++代码,以展示可能的反转过程,以便您对链表节点的反转有一个广泛的了解。

以上是将链表节点中的每个单词反转的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除