给出一个字母表和特殊字符的链表。在不影响特殊字符位置的情况下反转给定的链表。
null
例如：
输入 ：g->@->e->#->e->$->k->s->NULL 输出 ：s->@->k->#->e->$->e->g->NULL 解释 ：这里我们可以看到，在输出中，特殊字符在“不改变”和“链表”中的位置是相反的。
其思想是遍历链表，并将不包括特殊字符的字符存储在临时数组中。再次遍历链表，并以相反的方式将元素从数组复制到链表的节点。
下面是一步一步的算法 :
- 拿一个临时数组，TEMP_ARR。
- 遍历链表并执行以下操作
- 如果当前元素是字母表，则将链接列表中的该元素存储到TEMP_ARR。
- 否则，将节点指针增加1
- 再次从头部和末端遍历链表，并执行以下操作：
- 如果当前元素是字母表，则将TEMP_ARR的最后一个元素复制到当前链表节点，并为下一次迭代减少TEMP_ARR的当前索引。
- 否则，增加一个节点
以下是上述方法的实施情况：
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 current 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 = 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; } /* 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 current 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 current 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 { public char data; public 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 current 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 ) { Console.Write(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' ); Console.Write( "Given linked list: " ); printList(head); reverse(head, 13); Console.Write( "Reversed Linked list: " ); printList(head); } } // This code has been contributed // by 29AjayKumar |
Javascript
<script> // JavaScript program to reverse a // linked list without affecting // special characters // Link list node class Node { constructor() { let data,next; } } // Function to reverse the linked // list without affecting special // characters function reverse(head_ref,size) { let current = head_ref; let TEMP_ARR = new Array(size); let i = 0; // Traverse the linked list // and insert linked list // elements to TEMP_ARR while (current != null ) { // if the current data // is any alphabet than // store it in to TEMP_ARR if ((current.data.charCodeAt(0) >= 97 && current.data.charCodeAt(0) <= 122) || (current.data.charCodeAt(0) >= 65 && current.data.charCodeAt(0) <= 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.charCodeAt(0) >= 97 && current.data.charCodeAt(0) <= 122) || (current.data.charCodeAt(0) >= 65 && current.data.charCodeAt(0) <= 90)) { current.data = TEMP_ARR[--i]; current = current.next; } // else increase the node else current = current.next; } return head_ref; } // Function to push a node function push(head_ref,new_data) { /* allocate node */ let 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 */ function printList(head) { let temp = head; while (temp != null ) { document.write(temp.data); temp = temp.next; } } // Driver Code /* Start with the empty list */ let 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' ); document.write( "Given linked list: " ); printList(head); head=reverse(head, 13); document.write( "<br>Reversed Linked list: " ); printList(head); // This code is contributed by unknown2108 </script> |
输出：
Given linked list: geek$sforg#@eek$sReversed Linked list: skee$grofs#@kee$g
时间复杂性： O（N），其中N是链表中的节点总数。 辅助空间： O（N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
