Обратить узлы связанного списка, не затрагивая специальные символы

Опубликовано: 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}, прежде чем переходить к решению.

Идея состоит в том, чтобы пройти по связанному списку и сохранить символы, исключая специальные символы, во временном массиве. Снова просмотрите связанный список и скопируйте элементы из массива в узлы связанного списка в обратном порядке.

Ниже представлен пошаговый алгоритм :

  1. Возьмите временный массив TEMP_ARR.
  2. Просмотрите связанный список и выполните следующие действия.
    • если текущий элемент представляет собой алфавит, сохранить этот элемент связанного списка в TEMP_ARR.
    • иначе, увеличьте указатель узла на единицу
  3. Снова пройдитесь по связанному списку с головы и по 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
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022