Обратить узлы связанного списка, не затрагивая специальные символы
Опубликовано: 24 Января, 2022
Дан связанный список алфавитов и специальных символов. Переверните данный связанный список, не влияя на положение специальных символов.
Примеры:
Input: g -> @ -> e -> # -> e -> $ -> k -> s -> NULL
Output: s -> @ -> k -> # -> e -> $ -> e -> g -> NULL
Explanation: Here we can see that in the output the position of special character in not change and also linked list is reverse.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Идея состоит в том, чтобы пройти по связанному списку и сохранить символы, исключая специальные символы, во временном массиве. Снова просмотрите связанный список и скопируйте элементы из массива в узлы связанного списка в обратном порядке.
Ниже представлен пошаговый алгоритм :
- Возьмите временный массив TEMP_ARR.
- Просмотрите связанный список и выполните следующие действия.
- если текущий элемент представляет собой алфавит, сохранить этот элемент связанного списка в TEMP_ARR.
- иначе, увеличьте указатель узла на единицу
- Снова пройдитесь по связанному списку с головы и по TEMP_ARR с конца и сделайте следующее:
- если текущий элемент является алфавитом, скопируйте последний элемент TEMP_ARR в текущий узел связанного списка и уменьшите текущий индекс TEMP_ARR для следующей итерации.
- иначе, увеличьте узел на один
Below is the implementation of above approach:
C++
// C++ program to reverse a linked list // without affecting special characters #include <iostream> using namespace std; // Link list node struct Node { char data; struct Node* next; }; // Function to reverse the linked list // without affecting special characters void reverse( struct Node** head_ref, int size) { struct Node* current = *head_ref; char TEMP_ARR[size]; int i = 0; // Traverse the linked list and insert // linked list elements to TEMP_ARR while (current != NULL) { // if the cuurent data is any alphabet than // store it in to TEMP_ARR if ((current->data >= 97 && current->data <= 122) || (current->data >= 65 && current->data <= 90)) { TEMP_ARR[i++] = current->data; current = current->next; } // else increase the node position else current = current->next; } current = *head_ref; // Traverse the linked list again while (current != NULL) { // if current character is an alphabet than // replace the current element in the linked list // with the last element of the TEMP_ARR if ((current->data >= 97 && current->data <= 122) || (current->data >= 65 && current->data <= 90)) { current->data = TEMP_ARR[--i]; current = current->next; } // else increase the node else current = current->next; } } // Function to push a node void push( struct Node** head_ref, char new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print linked list */ 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() { /* Start with the empty list */ struct Node* head = NULL; push(&head, "s" ); push(&head, "$" ); push(&head, "k" ); push(&head, "e" ); push(&head, "e" ); push(&head, "@" ); push(&head, "#" ); push(&head, "g" ); push(&head, "r" ); push(&head, "o" ); push(&head, "f" ); push(&head, "s" ); push(&head, "$" ); push(&head, "k" ); push(&head, "e" ); push(&head, "e" ); push(&head, "g" ); cout << "Given linked list: " ; printList(head); reverse(&head, 13); cout << "
Reversed Linked list: " ; printList(head); return 0; } |
Java
// Java program to reverse a // linked list without affecting // special characters class GFG { // Link list node public static class Node { char data; Node next; } // Function to reverse the linked // list without affecting special // characters static void reverse(Node head_ref, int size) { Node current = head_ref; char TEMP_ARR[] = new char [size]; int i = 0 ; // Traverse the linked list // and insert linked list // elements to TEMP_ARR while (current != null ) { // if the cuurent data // is any alphabet than // store it in to TEMP_ARR if ((current.data >= 97 && current.data <= 122 ) || (current.data >= 65 && current.data <= 90 )) { TEMP_ARR[i++] = current.data; current = current.next; } // else increase the node position else current = current.next; } current = head_ref; // Traverse the linked list again while (current != null ) { // if current character is an // alphabet than replace the // current element in the linked // list with the last element // of the TEMP_ARR if ((current.data >= 97 && current.data <= 122 ) || (current.data >= 65 && current.data <= 90 )) { current.data = TEMP_ARR[--i]; current = current.next; } // else increase the node else current = current.next; } } // Function to push a node static Node push(Node head_ref, char new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list off the new node */ new_node.next = (head_ref); /* move the head to point to the new node */ (head_ref) = new_node; return head_ref; } /* Function to print linked list */ static void printList(Node head) { Node temp = head; while (temp != null ) { System.out.print(temp.data); temp = temp.next; } } // Driver Code public static void main(String rags[]) { /* Start with the empty list */ Node head = null ; head = push(head, "s" ); head = push(head, "$" ); head = push(head, "k" ); head = push(head, "e" ); head = push(head, "e" ); head = push(head, "@" ); head = push(head, "#" ); head = push(head, "g" ); head = push(head, "r" ); head = push(head, "o" ); head = push(head, "f" ); head = push(head, "s" ); head = push(head, "$" ); head = push(head, "k" ); head = push(head, "e" ); head = push(head, "e" ); head = push(head, "g" ); System.out.print( "Given linked list: " ); printList(head); reverse(head, 13 ); System.out.print( "
Reversed Linked list: " ); printList(head); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to reverse a linked list # without affecting special characters # Link list node class Node: def __init__( self , x): self .data = x self . next = None # Function to reverse the linked list # without affecting special characters def reverse(head_ref, size): current = head_ref TEMP_ARR = [ 0 for i in range ( 256 )] i = 0 # Traverse the linked list and insert # linked list elements to TEMP_ARR while (current ! = None ): # If the cuurent data is any alphabet than # store it in to TEMP_ARR if (( ord (current.data) > = 97 and ord (current.data) < = 122 ) or ( ord (current.data) > = 65 and ord (current.data) < = 90 )): TEMP_ARR[i] = current.data i + = 1 current = current. next # Else increase the node position else : current = current. next current = head_ref # Traverse the linked list again while (current ! = None ): # If current character is an alphabet # than replace the current element in # the linked list with the last element # of the TEMP_ARR if (( ord (current.data) > = 97 and ord (current.data) < = 122 ) or ( ord (current.data) > = 65 and ord (current.data) < = 90 )): i = i - 1 current.data = TEMP_ARR[i] current = current. next # Else increase the node else : current = current. next return head_ref # Function to push a node def push(head_ref, new_data): # Allocate node #new_node = (struct Node*)malloc(sizeof(struct Node)); # Put in the data new_node = Node(new_data) # Link the old list off the new node new_node. next = head_ref # Move the head to point to the new node head_ref = new_node return head_ref # Function to print linked list def printList(head): temp = head while (temp ! = None ): print (temp.data, end = "") temp = temp. next # Driver code if __name__ = = "__main__" : # Start with the empty list head = None head = push(head, "s" ) head = push(head, "$" ) head = push(head, "k" ) head = push(head, "e" ) head = push(head, "e" ) head = push(head, "@" ) head = push(head, "#" ) head = push(head, "g" ) head = push(head, "r" ) head = push(head, "o" ) head = push(head, "f" ) head = push(head, "s" ) head = push(head, "$" ) head = push(head, "k" ) head = push(head, "e" ) head = push(head, "e" ) head = push(head, "g" ) print ( "Given linked list: " , end = "") printList(head) head = reverse(head, 13 ) print ( "
Reversed Linked list: " , end = "") printList(head) # This code is contributed by mohit kumar 29 |
C#
// C# program to reverse a // linked list without affecting // special characters using System; class GFG { // Link list node public class Node РЕКОМЕНДУЕМЫЕ СТАТЬИ |