Решење са повезницом са Палиндромом  


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Блоомберг Цапитал Оне Цисцо фацебоок гоогле Гроб интел ИКСЛ мицрософт Нутаник пророчанство Паитм Снапцхат Убер иандек
алгоритми шифрирање Интервју интервјупреп ЛеетЦоде ЛеетЦодеСолутионс Повезана листа Тво Поинтерс

У проблему „Листа повезаних с палиндромом“ морамо да проверимо да ли је дати појединачно цео број повезана листа је палиндром или није.

Пример  

List = {1 -> 2 -> 3 -> 2 -> 1}
true

Објашњење # 1: Листа је палиндром јер су сви елементи од почетка и назад једнаке вредности.

List = {1 -> 2 -> 3 -> 4 -> 5}
false

Објашњење # 2: Листа није палиндром јер елементи напред и назад нису исти.

Приступ(Рекурзије 

То је лако приметити да морамо да имамо детаље о чворовима са задње стране низа за проверу својстава палиндрома. У овом случају имамо појединачно повезана листа, што значи да можемо само да се крећемо унапред да бисмо дошли до било ког чвора. Стога постаје важно користити неку структуру података за држање чворова са задње стране, нпр стек је могућа опција јер задржава најновији чвор на врху. Такође можемо користити рекурзију слично. Рекурзија је елегантно добити вредности чворова у обрнутом редоследу. За боље разумевање размотрите доњи општи псеудокод:

inorderTraversal(root)
{
    if(root == null)
        return;
    inorderTraversal(root.left);
    print(root.data);
    inorderTraversal(root.right);
}

Прво се исписује горњи код left (остављено) чворова у стаблу, јер рекурзивно позивамо функцију да иде у лево подређено тело било корена пре штампања вредности самог чвора. Слично томе, можемо користити рекурзија да бисмо прво отишли ​​на последње чворове и када ће се функција вратити, добићемо вредности чворова у обрнутом редоследу. Користићемо променљиву за итерацију напред, на коју рекурзија неће утицати. На тај начин можемо упоредити вредност итератора напред и вредност обрнутог чвора добијене рекурзијом да бисмо упоредили елементе.

Види такође
Дефангинг ИП Аддресс Леетцоде решење

Алгоритам

  1. Функција исПалиндроме () користи се за враћање да ли је листа са глава да ли је палиндром или није
  2. Прогласимо члана података класе именованим предњи за чување чворова за напредне итерације
  3. In исПалиндром ():
    • Инитиализе предња = глава
    • ретурн палиндромеЦхецк (глава)
  4. In палиндромеЦхецк (струја):
    • If струја is нула:
      • повратак прави
    • If палиндромеЦхецк (тренутни.наредни) is лажан:
      • повратак лажан
    • If Тренутна вредност is не једнако фронт.валуе
      • повратак лажан
    • прираст напред као:
      • фронт = фронт.нект
    • повратак прави пошто смо извршили све провере
  5. Одштампајте резултат

Примена решења за мрежни списак са повезаном листом Палиндроме

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

bool palindromeCheck(listNode* head)
{
    if(head == NULL)
        return true;
    if(!palindromeCheck(head->next))
        return false;
    if(front->value != head->value)
        return false;
    front = front->next;
    return true;
}

bool isPalindrome(listNode* head)
{
    front = head;
    return palindromeCheck(head);
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Јава Програм

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    static listNode front;
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static boolean palindromeCheck(listNode head)
    {
        if(head == null)
            return true;
        if(!palindromeCheck(head.next))
            return false;
        if(front.value != head.value)
            return false;
        front = front.next;
        return true;
    }

    static boolean isPalindrome(listNode head)
    {
        front = head;
        return palindromeCheck(head);
    }
}
true

Анализа сложености решења са ретким кодом повезане са палиндромом

Сложеност времена

НА) док једном прелазимо листу користећи рекурзију. Овде је Н = број чворова на листи.

Види такође
Серијализовати и десеријализовати бинарно стабло

Сложеност простора

НА) како називамо рекурзивну функцију за проверу сваког чвора који се ствара N сложите оквире у меморији.

Приступ (обрнута друга половина)  

Једини начин да се решите простора који се користи у рекурзији је да измените дату листу на месту. Преокрећемо другу половину повезане листе, а затим користимо два итератора унапред за обе половине да бисмо проверили да ли су одговарајуће вредности једнаке. За овај процес морамо:

  • пронађите средину листе да бисмо могли да преокренемо другу половину.
  • створити функцију за преокрет друге половине листе
  • проверите да ли су прво и друго полувреме једнаке

Све наведено може се обавити у линеарном времену. Након што преокренемо повезану листу, започињемо проверу док се друго полувреме не заврши.

Решење са повезницом са Палиндромом

Алгоритам

  1. If глава is нула:
    • ретурн труе
  2. Пронађите средину повезане листе помоћу миддлеОфЛист (главаfunkcija:
    • Иницијализујте два показивача успорити брзо обојица показујући на главу списка
    • До брзо.напријед фаст.нект.нект су обоје не нула:
      1. Повећање успорити до 1, споро = споро.напријед
      2. Повећање брзо до 2, фаст = фаст.нект.нект
    • успорити показивач сада показује на средину листе
    • повратак успорити
  3. Сада окрећемо другу половину позива реверсеЛист (хеад = средњи.даље) функција
    • Инитиалисе прев = нула
    • док глава није нулл:
      • Спремите следећи чвор у привремену променљиву, као следећи
      • Преокрените смер показивача помоћу хеад.нект = прев
      • прев = глава
      • Померите се на листи користећи глава = следећа
    • повратак прев
  4. Сада инцијализујте два показивача птрКСНУМКС птрКСНУМКС да прође кроз обе половине:
    1. птр1 = глава
    2. птр2 = старт другог полувремена
    3. док птрКСНУМКС није нулл:
      1. if птрКСНУМКС.вредност није једнак птрКСНУМКС.вредност
        1. повратак лажан
    4. повратак прави као што смо проверили сваки чвор у првој и другој половини
  5. Одштампајте резултат
Види такође
К Празни слотови ЛеетЦоде

Примена решења за мрежни списак са повезаном листом Палиндроме

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* middleOfList(listNode* head)
{
    listNode *slow = head , *fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

listNode* reverseList(listNode* head)
{
    listNode *prev = NULL;
    while(head != NULL)
    {
        listNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(listNode* head)
{
    if(head == NULL)
        return true;
    listNode* middleNode = middleOfList(head);
    listNode* startOfSecondHalf = reverseList(middleNode->next);

    listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
    while(ptr2 != NULL)
    {
        if(ptr1->value != ptr2->value)
            return false;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return true;
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Јава Програм

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static listNode middleOfList(listNode head)
    {
        listNode slow = head , fast = head;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static listNode reverseList(listNode head)
    {
        listNode prev = null;
        while(head != null)
        {
            listNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(listNode head)
    {
        if(head == null)
            return true;
        listNode middleNode = middleOfList(head);
        listNode startOfSecondHalf = reverseList(middleNode.next);

        listNode ptr1 = head , ptr2 = startOfSecondHalf;
        while(ptr2 != null)
        {
            if(ptr1.value != ptr2.value)
                return false;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return true;
    }
}
true

Анализа сложености решења са ретким кодом повезане са палиндромом

Сложеност времена

НА) док помоћу линеарних петљи проналазимо средину листе, преокрећемо је и упоређујемо обе половине. Ево, N = величина листе.

Види такође
Минимални размени потребни за повезивање свих елемената мањих или једнаких к

Сложеност простора

О (1) пошто користимо само стални додатни простор.