Рубрики

Функция, чтобы проверить, является ли односвязный список палиндромом

Учитывая односвязный список символов, напишите функцию, которая возвращает истину, если заданный список является палиндромом, иначе ложь.

МЕТОД 1 (Используйте Стек)

  • Простое решение — использовать стек узлов списка. Это в основном включает три шага.
  • Пройдите по заданному списку от головы до хвоста и поместите каждый посещенный узел в стек.
  • Пройдите по списку еще раз. Для каждого посещенного узла извлеките узел из стека и сравните данные извлеченного узла с текущим посещенным узлом.
  • Если все узлы совпадают, вернуть true, иначе false.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

CPP

#include<bits/stdc++.h>

using namespace std; 

  

class Node {

public:

        int data;

        Node(int d){

            data = d;

        }

        Node *ptr;

};

  
// Функция для проверки наличия связанного списка
// палиндром или нет

bool isPalin(Node* head){

          

        // Temp указатель

        Node* slow= head;

  

        // Объявляем стек

        stack <int> s;

   

  

        // выдвигаем все элементы списка

        // в стек

        while(slow != NULL){

                s.push(slow->data);

  

                // Двигаться вперед

                slow = slow->ptr;

        }

  

        // Повторяем в списке снова и

        // проверка, выскочив из стека

        while(head != NULL ){

              

            // Получить самый верхний элемент

             int i=s.top();

  

             // Высовываем элемент

             s.pop();

  

             // Проверяем, нет ли данных

             // так же, как всплывающий элемент

            if(head -> data != i){

                return false;

            }

  

            // Двигаться вперед

           head=head->ptr;

        }

  

return true;

}

  
// Код драйвера

int main(){

  

    // Добавление связанного списка

    Node one =  Node(1);

    Node two = Node(2);

    Node three = Node(3);

    Node four = Node(2);

    Node five = Node(1);

  

    // Инициализируем следующий указатель

    // каждого текущего указателя

    five.ptr = NULL;

    one.ptr = &two;

    two.ptr = &three;

    three.ptr = &four;

    four.ptr = &five;

    Node* temp = &one;

  

      

    // Вызываем функцию для проверки палиндрома или нет

    int result = isPalin(&one);

    

    if(result == 1)

            cout<<"isPalindrome is true\n";

    else

        cout<<"isPalindrome is true\n";

  

return 0;

}

  
// Этот код предоставлен Striver

Джава

/ * Java-программа для проверки рекурсивности связанного списка * /

import java.util.*;

  

class linkeList {

    public static void main(String args[])

    {

        Node one = new Node(1);

        Node two = new Node(2);

        Node three = new Node(3);

        Node four = new Node(4);

        Node five = new Node(3);

        Node six = new Node(2);

        Node seven = new Node(1);

        one.ptr = two;

        two.ptr = three;

        three.ptr = four;

        four.ptr = five;

        five.ptr = six;

        six.ptr = seven;

        boolean condition = isPalindrome(one);

        System.out.println("isPalidrome :" + condition);

    }

    static boolean isPalindrome(Node head)

    {

  

        Node slow = head;

        boolean ispalin = true;

        Stack<Integer> stack = new Stack<Integer>();

  

        while (slow != null) {

            stack.push(slow.data);

            slow = slow.ptr;

        }

  

        while (head != null) {

  

            int i = stack.pop();

            if (head.data == i) {

                ispalin = true;

            }

            else {

                ispalin = false;

                break;

            }

            head = head.ptr;

        }

        return ispalin;

    }

}

  

class Node {

    int data;

    Node ptr;

    Node(int d)

    {

        ptr = null;

        data = d;

    }

}

Выход

 isPalindrome: true

Временная сложность описанного выше метода составляет O (n).


МЕТОД 2 (переворачивая список)

Этот метод занимает O (n) времени и O (1) дополнительного пространства.
1) Получить середину связанного списка.
2) Переверните вторую половину связанного списка.
3) Проверьте, идентичны ли первая половина и вторая половина.
4) Создайте исходный связанный список, перевернув вторую половину снова и прикрепив его обратно к первой половине.

Чтобы разделить список на две половины, используется метод 2 этого поста.
Когда число узлов четное, первая и вторая половина содержат ровно половину узлов. Сложность в этом методе — справиться со случаем, когда количество узлов нечетное. Мы не хотим, чтобы средний узел был частью какого-либо из списков, так как мы собираемся сравнить их на равенство. В нечетном случае мы используем отдельную переменную 'midnode'.

С

/ * Программа для проверки, является ли связанный список палиндромом * /
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел списка ссылок * /

struct Node {

    char data;

    struct Node* next;

};

  

void reverse(struct Node**);

bool compareLists(struct Node*, struct Node*);

  
/ * Функция, чтобы проверить, является ли данный связанный список

  палиндром или нет * /

bool isPalindrome(struct Node* head)

{

    struct Node *slow_ptr = head, *fast_ptr = head;

    struct Node *second_half, *prev_of_slow_ptr = head;

    struct Node* midnode = NULL; // Для обработки списка нечетных размеров

    bool res = true; // инициализировать результат

  

    if (head != NULL && head->next != NULL) {

        / * Получить середину списка. Переместить slow_ptr на 1

          и fast_ptrr на 2, slow_ptr будет иметь середину

          узел * /

        while (fast_ptr != NULL && fast_ptr->next != NULL) {

            fast_ptr = fast_ptr->next->next;

  

            / * Нам нужен предыдущий из slow_ptr для

             связанные списки с нечетными элементами * /

            prev_of_slow_ptr = slow_ptr;

            slow_ptr = slow_ptr->next;

        }

  

        / * fast_ptr станет NULL, если в списке есть даже элементы.

           И не NULL для нечетных элементов. Нам нужно пропустить средний узел

           для нечетного случая и сохранить его где-нибудь, чтобы мы могли восстановить

           оригинальный список * /

        if (fast_ptr != NULL) {

            midnode = slow_ptr;

            slow_ptr = slow_ptr->next;

        }

  

        // Теперь переверните вторую половину и сравните ее с первой половиной

        second_half = slow_ptr;

        prev_of_slow_ptr->next = NULL; // NULL завершить первую половину

        reverse(&second_half); // Обратный ход второй половины

        res = compareLists(head, second_half); // сравнить

  

        / * Построить исходный список обратно * /

        reverse(&second_half); // Снова перевернуть вторую половину

  

        // Если был средний узел (случай нечетного размера), который

        // не был частью ни первой половины, ни второй половины.

        if (midnode != NULL) {

            prev_of_slow_ptr->next = midnode;

            midnode->next = second_half;

        }

        else

            prev_of_slow_ptr->next = second_half;

    }

    return res;

}

  
/ * Функция для обратного связанного списка Обратите внимание, что это

    функция может изменить голову * /

void reverse(struct Node** head_ref)

{

    struct Node* prev = NULL;

    struct Node* current = *head_ref;

    struct Node* next;

    while (current != NULL) {

        next = current->next;

        current->next = prev;

        prev = current;

        current = next;

    }

    *head_ref = prev;

}

  
/ * Функция для проверки, если два списка ввода имеют одинаковые данные * /

bool compareLists(struct Node* head1, struct Node* head2)

{

    struct Node* temp1 = head1;

    struct Node* temp2 = head2;

  

    while (temp1 && temp2) {

        if (temp1->data == temp2->data) {

            temp1 = temp1->next;

            temp2 = temp2->next;

        }

        else

            return 0;

    }

  

    / * Оба пустых возвращаются 1 * /

    if (temp1 == NULL && temp2 == NULL)

        return 1;

  

    / * Достигнет здесь, когда один равен NULL

      а другой нет *

    return 0;

}

  
/ * Переместить узел в связанный список. Обратите внимание, что эта функция

  меняет голову * /

void push(struct Node** head_ref, char new_data)

{

    / * выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову в почар на новый узел * /

    (*head_ref) = new_node;

}

  
// Утилита для печати заданного связанного списка

void printList(struct node* ptr)

{

    while (ptr != NULL) {

        printf("%c->", ptr->data);

        ptr = ptr->next;

    }

    printf("NULL\n");

}

  
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

    char str[] = "abacaba";

    int i;

  

    for (i = 0; str[i] != '\0'; i++) {

        push(&head, str[i]);

        printList(head);

        isPalindrome(head) ? printf("Is Palindrome\n\n") : printf("Not Palindrome\n\n");

    }

  

    return 0;

}

Джава

/ * Java-программа для проверки, является ли связанный список палиндромом * /

  

class LinkedList {

    Node head; // заголовок списка

    Node slow_ptr, fast_ptr, second_half;

  

    / * Узел связанного списка * /

    class Node {

        char data;

        Node next;

  

        Node(char d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Функция, чтобы проверить, является ли данный связанный список

       палиндром или нет * /

    boolean isPalindrome(Node head)

    {

        slow_ptr = head;

        fast_ptr = head;

        Node prev_of_slow_ptr = head;

        Node midnode = null; // Для обработки списка нечетных размеров

        boolean res = true; // инициализировать результат

  

        if (head != null && head.next != null) {

            / * Получить середину списка. Переместить slow_ptr на 1

               и fast_ptrr на 2, slow_ptr будет иметь середину

               узел * /

            while (fast_ptr != null && fast_ptr.next != null) {

                fast_ptr = fast_ptr.next.next;

  

                / * Нам нужен предыдущий из slow_ptr для

                  связанные списки с нечетными элементами * /

                prev_of_slow_ptr = slow_ptr;

                slow_ptr = slow_ptr.next;

            }

  

            / * fast_ptr станет NULL, когда есть даже элементы

               в списке, а не NULL для нечетных элементов. Нам нужно пропустить

               средний узел для нечетного случая и хранить его где-то так, чтобы

               мы можем восстановить первоначальный список * /

            if (fast_ptr != null) {

                midnode = slow_ptr;

                slow_ptr = slow_ptr.next;

            }

  

            // Теперь переверните вторую половину и сравните ее с первой половиной

            second_half = slow_ptr;

            prev_of_slow_ptr.next = null; // NULL завершить первую половину

            reverse(); // Обратный ход второй половины

            res = compareLists(head, second_half); // сравнить

  

            / * Построить исходный список обратно * /

            reverse(); // Снова перевернуть вторую половину

  

            if (midnode != null) {

                // Если был средний узел (случай нечетного размера), который

                // не был частью ни первой половины, ни второй половины.

                prev_of_slow_ptr.next = midnode;

                midnode.next = second_half;

            }

            else

                prev_of_slow_ptr.next = second_half;

        }

        return res;

    }

  

    / * Функция для обратного связанного списка Обратите внимание, что это

       функция может изменить голову * /

    void reverse()

    {

        Node prev = null;

        Node current = second_half;

        Node next;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        second_half = prev;

    }

  

    / * Функция для проверки, если два списка ввода имеют одинаковые данные * /

    boolean compareLists(Node head1, Node head2)

    {

        Node temp1 = head1;

        Node temp2 = head2;

  

        while (temp1 != null && temp2 != null) {

            if (temp1.data == temp2.data) {

                temp1 = temp1.next;

                temp2 = temp2.next;

            }

            else

                return false;

        }

  

        / * Оба пустых возвращаются 1 * /

        if (temp1 == null && temp2 == null)

            return true;

  

        / * Достигнет здесь, когда один равен NULL

           а другой нет *

        return false;

    }

  

    / * Переместить узел в связанный список. Обратите внимание, что эта функция

       меняет голову * /

    public void push(char new_data)

    {

        / * Выделить узел &

           Введите данные * /

        Node new_node = new Node(new_data);

  

        / * связать старый список с новым * /

        new_node.next = head;

  

        / * Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    // Утилита для печати заданного связанного списка

    void printList(Node ptr)

    {

        while (ptr != null) {

            System.out.print(ptr.data + "->");

            ptr = ptr.next;

        }

        System.out.println("NULL");

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args)

    {

  

        / * Начнем с пустого списка * /

        LinkedList llist = new LinkedList();

  

        char str[] = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' };

        String string = new String(str);

        for (int i = 0; i < 7; i++) {

            llist.push(str[i]);

            llist.printList(llist.head);

            if (llist.isPalindrome(llist.head) != false) {

                System.out.println("Is Palindrome");

                System.out.println("");

            }

            else {

                System.out.println("Not Palindrome");

                System.out.println("");

            }

        }

    }

}

C #

/ * C # программа для проверки, является ли связанный список палиндромом * /

using System;

class LinkedList {

    Node head; // заголовок списка

    Node slow_ptr, fast_ptr, second_half;

  

    / * Узел связанного списка * /

    public class Node {

        public char data;

        public Node next;

  

        public Node(char d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Функция, чтобы проверить, является ли данный связанный список

       палиндром или нет * /

    Boolean isPalindrome(Node head)

    {

        slow_ptr = head;

        fast_ptr = head;

        Node prev_of_slow_ptr = head;

        Node midnode = null; // Для обработки списка нечетных размеров

        Boolean res = true; // инициализировать результат

  

        if (head != null && head.next != null) {

            / * Получить середину списка. Переместить slow_ptr на 1

               и fast_ptrr на 2, slow_ptr будет иметь середину

               узел * /

            while (fast_ptr != null && fast_ptr.next != null) {

                fast_ptr = fast_ptr.next.next;

  

                / * Нам нужен предыдущий из slow_ptr для

                  связанные списки с нечетными элементами * /

                prev_of_slow_ptr = slow_ptr;

                slow_ptr = slow_ptr.next;

            }

  

            / * fast_ptr станет NULL, когда есть даже элементы

               в списке, а не NULL для нечетных элементов. Нам нужно пропустить

               средний узел для нечетного случая и хранить его где-то так, чтобы

               мы можем восстановить первоначальный список * /

            if (fast_ptr != null) {

                midnode = slow_ptr;

                slow_ptr = slow_ptr.next;

            }

  

            // Теперь переверните вторую половину и сравните ее с первой половиной

            second_half = slow_ptr;

            prev_of_slow_ptr.next = null; // NULL завершить первую половину

            reverse(); // Обратный ход второй половины

            res = compareLists(head, second_half); // сравнить

  

            / * Построить исходный список обратно * /

            reverse(); // Снова перевернуть вторую половину

  

            if (midnode != null) {

                // Если был средний узел (случай нечетного размера), который

                // не был частью ни первой половины, ни второй половины.

                prev_of_slow_ptr.next = midnode;

                midnode.next = second_half;

            }

            else

                prev_of_slow_ptr.next = second_half;

        }

        return res;

    }

  

    / * Функция для обратного связанного списка Обратите внимание, что это

       функция может изменить голову * /

    void reverse()

    {

        Node prev = null;

        Node current = second_half;

        Node next;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        second_half = prev;

    }

  

    / * Функция для проверки, если два списка ввода имеют одинаковые данные * /

    Boolean compareLists(Node head1, Node head2)

    {

        Node temp1 = head1;

        Node temp2 = head2;

  

        while (temp1 != null && temp2 != null) {

            if (temp1.data == temp2.data) {

                temp1 = temp1.next;

                temp2 = temp2.next;

            }

            else

                return false;

        }

  

        / * Оба пустых возвращаются 1 * /

        if (temp1 == null && temp2 == null)

            return true;

  

        / * Достигнет здесь, когда один равен NULL

           а другой нет *

        return false;

    }

  

    / * Переместить узел в связанный список. Обратите внимание, что эта функция

       меняет голову * /

    public void push(char new_data)

    {

        / * Выделить узел &

           Введите данные * /

        Node new_node = new Node(new_data);

  

        / * связать старый список с новым * /

        new_node.next = head;

  

        / * Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    // Утилита для печати заданного связанного списка

    void printList(Node ptr)

    {

        while (ptr != null) {

            Console.Write(ptr.data + "->");

            ptr = ptr.next;

        }

        Console.WriteLine("NULL");

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void Main(String[] args)

    {

  

        / * Начнем с пустого списка * /

        LinkedList llist = new LinkedList();

  

        char[] str = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' };

  

        for (int i = 0; i < 7; i++) {

            llist.push(str[i]);

            llist.printList(llist.head);

            if (llist.isPalindrome(llist.head) != false) {

                Console.WriteLine("Is Palindrome");

                Console.WriteLine("");

            }

            else {

                Console.WriteLine("Not Palindrome");

                Console.WriteLine("");

            }

        }

    }

}
// Этот код предоставлен Арнабом Кунду


Выход:

a->NULL
Palindrome

b->a->NULL
Not Palindrome

a->b->a->NULL
Is Palindrome

c->a->b->a->NULL
Not Palindrome

a->c->a->b->a->NULL
Not Palindrome

b->a->c->a->b->a->NULL
Not Palindrome

a->b->a->c->a->b->a->NULL
Is Palindrome

Сложность времени: O (n)
Вспомогательное пространство: O (1)

МЕТОД 3 (Использование рекурсии)
Используйте два указателя влево и вправо. Двигайтесь вправо и влево, используя рекурсию, и проверяйте последовательность в каждом рекурсивном вызове.
1) Подсписок — палиндром.
2) Значения на текущий слева и справа совпадают.

Если оба вышеуказанных условия верны, верните истину.

Идея состоит в том, чтобы использовать стек вызовов функций в качестве контейнера. Рекурсивно пройти до конца списка. Когда мы вернемся с последнего значения NULL, мы будем на последнем узле. Последний узел для сравнения с первым узлом списка.

Чтобы получить доступ к первому узлу списка, нам нужно, чтобы заголовок списка был доступен при последнем вызове рекурсии. Следовательно, мы передаем голову и рекурсивной функции. Если они совпадают, нам нужно сравнить (2, n-2) узлов. Опять же, когда рекурсия возвращается к (n-2) -ому узлу, нам нужна ссылка на 2-й узел из головы. Мы продвигаем указатель головы в предыдущем вызове, чтобы обратиться к следующему узлу в списке.

Однако хитрость в выявлении двойного указателя. Передача одного указателя так же хороша, как и передача по значению, и мы передадим один и тот же указатель снова и снова. Нам нужно передать адрес указателя головы для отражения изменений в родительских рекурсивных вызовах.

Спасибо Sharad Chandra за предложенный подход.

С

// Рекурсивная программа для проверки, является ли данный связанный список палиндромом
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел списка ссылок * /

struct node {

    char data;

    struct node* next;

};

  
// Начальные параметры этой функции: & head и head

bool isPalindromeUtil(struct node** left, struct node* right)

{

    / * остановить рекурсию, когда право становится NULL * /

    if (right == NULL)

        return true;

  

    / * Если подсписок не является палиндромом, то нет необходимости

       проверить текущие значения влево и вправо, вернуть false * /

    bool isp = isPalindromeUtil(left, right->next);

    if (isp == false)

        return false;

  

    / * Проверить значения в текущей левой и правой * /

    bool isp1 = (right->data == (*left)->data);

  

    / * Перейти влево к следующему узлу * /

    *left = (*left)->next;

  

    return isp1;

}

  
// Обёртка над isPalindromeUtil ()

bool isPalindrome(struct node* head)

{

    isPalindromeUtil(&head, head);

}

  
/ * Переместить узел в связанный список. Обратите внимание, что эта функция

  меняет голову * /

void push(struct node** head_ref, char new_data)

{

    / * выделить узел * /

    struct node* new_node = (struct node*)malloc(sizeof(struct node));

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову в почар на новый узел * /

    (*head_ref) = new_node;

}

  
// Утилита для печати заданного связанного списка

void printList(struct node* ptr)

{

    while (ptr != NULL) {

        printf("%c->", ptr->data);

        ptr = ptr->next;

    }

    printf("NULL\n");

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    / * Начнем с пустого списка * /

    struct node* head = NULL;

    char str[] = "abacaba";

    int i;

  

    for (i = 0; str[i] != '\0'; i++) {

        push(&head, str[i]);

        printList(head);

        isPalindrome(head) ? printf("Is Palindrome\n\n") : printf("Not Palindrome\n\n");

    }

  

    return 0;

}

Джава

/ * Java-программа для проверки рекурсивности связанного списка * /

  

class LinkedList {

    Node head; // заголовок списка

    Node left;

  

    / * Узел связанного списка * /

    class Node {

        char data;

        Node next;

  

        Node(char d)

        {

            data = d;

            next = null;

        }

    }

  

    // Начальные параметры этой функции: & head и head

    boolean isPalindromeUtil(Node right)

    {

        left = head;

  

        / * остановить рекурсию, когда право становится NULL * /

        if (right == null)

            return true;

  

        / * Если подсписок не является палиндромом, то нет необходимости

           проверить текущие значения влево и вправо, вернуть false * /

        boolean isp = isPalindromeUtil(right.next);

        if (isp == false)

            return false;

  

        / * Проверить значения в текущей левой и правой * /

        boolean isp1 = (right.data == (left).data);

  

        / * Перейти влево к следующему узлу * /

        left = left.next;

  

        return isp1;

    }

  

    // Обёртка над isPalindromeUtil ()

    boolean isPalindrome(Node head)

    {

        boolean result = isPalindromeUtil(head);

        return result;

    }

  

    / * Переместить узел в связанный список. Обратите внимание, что эта функция

       меняет голову * /

    public void push(char new_data)

    {

        / * Выделить узел &

           Введите данные * /

        Node new_node = new Node(new_data);

  

        / * связать старый список с новым * /

        new_node.next = head;

  

        / * Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    // Утилита для печати заданного связанного списка

    void printList(Node ptr)

    {

        while (ptr != null) {

            System.out.print(ptr.data + "->");

            ptr = ptr.next;

        }

        System.out.println("NULL");

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args)

    {

        / * Начнем с пустого списка * /

        LinkedList llist = new LinkedList();

  

        char str[] = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' };

        String string = new String(str);

        for (int i = 0; i < 7; i++) {

            llist.push(str[i]);

            llist.printList(llist.head);

            if (llist.isPalindrome(llist.head) != false) {

                System.out.println("Is Palindrome");

                System.out.println("");

            }

            else {

                System.out.println("Not Palindrome");

                System.out.println("");

            }

        }

    }

}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

C #

/ * C # программа для проверки наличия связанного списка
палиндром рекурсивно * /

using System;

      

public class LinkedList 

    Node head; // заголовок списка

    Node left; 

  

    / * Узел связанного списка * /

    public class Node 

    

        public char data; 

        public Node next; 

  

        public Node(char d) 

        

            data = d; 

            next = null

        

    

  

    // Начальные параметры этой функции: & head и head

    Boolean isPalindromeUtil(Node right) 

    

        left = head; 

  

        / * остановить рекурсию, когда право становится NULL * /

        if (right == null

            return true

  

        / * Если подсписок не является палиндромом, то нет необходимости

        проверить текущие значения влево и вправо, вернуть false * /

        Boolean isp = isPalindromeUtil(right.next); 

        if (isp == false

            return false

  

        / * Проверить значения в текущей левой и правой * /

        Boolean isp1 = (right.data == (left).data); 

  

        / * Перейти влево к следующему узлу * /

        left = left.next; 

  

        return isp1; 

    

  

    // Обёртка над isPalindromeUtil ()

    Boolean isPalindrome(Node head) 

    

        Boolean result = isPalindromeUtil(head); 

        return result; 

    

  

    / * Переместить узел в связанный список. Обратите внимание, что эта функция

    меняет голову * /

    public void push(char new_data) 

    

        / * Выделить узел &

        Введите данные * /

        Node new_node = new Node(new_data); 

  

        / * связать старый список с новым * /

        new_node.next = head; 

  

        / * Переместить голову, чтобы указать на новый узел * /

        head = new_node; 

    

  

    // Утилита для печати заданного связанного списка

    void printList(Node ptr) 

    

        while (ptr != null

        

            Console.Write(ptr.data + "->"); 

            ptr = ptr.next; 

        

        Console.WriteLine("NULL"); 

    

  

    / * Код водителя * /

    public static void Main(String[] args) 

    

        / * Начнем с пустого списка * /

        LinkedList llist = new LinkedList(); 

  

        char []str = { 'a', 'b', 'a', 'c', 'a', 'b', 'a' }; 

        // String string = new String (str);

        for (int i = 0; i < 7; i++) { 

            llist.push(str[i]); 

            llist.printList(llist.head); 

            if (llist.isPalindrome(llist.head) != false

            

                Console.WriteLine("Is Palindrome"); 

                Console.WriteLine(""); 

            

            else 

            

                Console.WriteLine("Not Palindrome"); 

                Console.WriteLine(""); 

            

        

    

  
// Этот код предоставлен Rajput-Ji


Выход:

a->NULL
Not Palindrome

b->a->NULL
Not Palindrome

a->b->a->NULL
Is Palindrome

c->a->b->a->NULL
Not Palindrome

a->c->a->b->a->NULL
Not Palindrome

b->a->c->a->b->a->NULL
Not Palindrome

a->b->a->c->a->b->a->NULL
Is Palindrome

Сложность времени: O (n)
Вспомогательное пространство: O (n), если учитывается размер стека вызова функции, в противном случае O (1).

Рекомендуемые посты:

Функция, чтобы проверить, является ли односвязный список палиндромом

0.00 (0%) 0 votes