Паліндром звязаны спіс Leetcode рашэнне


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка яблык Bloomberg Capital One Cisco facebook Google Магіла Intel IXL Microsoft Нутанікс Аракул Paytm Snapchat Uber Яндэкс
Звязаны спіс Два паказальнікі

У задачы "Спіс звязаных з паліндромам" мы павінны праверыць, ці з'яўляецца дадзены адзінкавы цэлы лік звязаны спіс паліндром ці не.

Прыклад

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);
}

Прыведзены вышэй код спачатку раздрукоўвае пакінуць вузлы ў дрэве, таму што мы рэкурсіўна выклікаем функцыю пераходу да левых даччыных частак любога кораня перад тым, як надрукаваць значэнне самога вузла. Аналагічным чынам мы можам выкарыстоўваць рэкурсія каб перайсці да апошніх вузлоў першымі, і калі функцыя будзе вяртацца назад, мы атрымаем значэнні вузлоў у зваротным парадку. Мы будзем выкарыстоўваць зменную для ітэрацыі наперад, на якую рэкурсія не паўплывае. Такім чынам, мы можам параўнаць значэнне ітэратара наперад і значэнне зваротнага вузла, атрыманыя рэкурсіяй, для параўнання элементаў.

Алгарытм

  1. Функцыя isPalindrome () выкарыстоўваецца для вяртання таго, ці будзе спіс з галава паліндром ці не
  2. Мы абвяшчаем названага члена класа перад для захоўвання вузлоў для праходжання ітэрацый
  3. In isPalindrom ():
    • ініцыялізаваць спераду = галава
    • зваротны паліндромCheck (галава)
  4. In palindromeCheck (ток):
    • If ток is нуля:
      • вяртаць праўда
    • If palindromeCheck (бягучы.далей) is ілжывы:
      • вяртаць ілжывы
    • If бягучая.значэнне is ня роўна спераду.значэнне
      • вяртаць ілжывы
    • павялічыць фронт як:
      • спераду = спераду.далей
    • вяртаць праўда як мы выконвалі ўсе праверкі
  5. Раздрукуйце вынік

Рэалізацыя рашэння Leetcode са звязаным спісам Palindrome

Праграма C ++

#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;
}

Праграма Java

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

Аналіз складанасці рашэння з выкарыстаннем спісу палітромаў з выкарыстаннем штрых-кода

Складанасць часу

O (N) як мы пераходзім спіс адзін раз, выкарыстоўваючы рэкурсію. Тут N = колькасць вузлоў у спісе.

Касмічная складанасць

O (N) як мы называем рэкурсіўную функцыю для праверкі кожнага ствараемага вузла N стэк кадраў у памяці.

Падыход (зваротная іншая палова)

Адзіны спосаб пазбавіцца ад прасторы, якая выкарыстоўваецца ў рэкурсіі, - змяніць дадзены спіс на месцы. Мы адмяняем другую палову звязанага спісу, а затым выкарыстоўваем два ітэратары для абедзвюх палоў, каб праверыць, ці адпавядаюць адпаведныя значэнні. Для гэтага працэсу нам трэба:

  • знайдзіце сярэдзіну спісу, каб мы маглі пераламаць другую палову.
  • стварыць функцыю, каб адмяніць другую палову спісу
  • праверыць, ці роўная першая і другая палова

Усё вышэйсказанае можна зрабіць у лінейны час. Пасля таго, як мы скасуем звязаны спіс, мы пачынаем праверку да завяршэння другой паловы.

Паліндром звязаны спіс Leetcode рашэнне

Алгарытм

  1. If галава is нуля:
    • вяртанне праўда
  2. Знайдзіце сярэдзіну звязанага спісу, выкарыстоўваючы middleOfList (галавафункцыя:
    • Ініцыялізаваць два паказальнікі павольны і хутка абодва паказваючы на ​​галоўку спісу
    • Да хуткі.далей і fast.next.next абодва ня нуль:
      1. инкремент павольны да 1 г. slow = slow.next
      2. инкремент хутка да 2 г. хуткі = хуткі. наступны. наступны
    • павольны паказальнік цяпер паказвае на сярэдзіну спіса
    • вяртаць павольны
  3. Цяпер мы адмяняем другую палову спіса reverseList (галава = сярэдні.далей) функцыя
    • Ініцыялізацыя Папярэдняя = нуля
    • у той час як галава не роўна нулю:
      • Захоўваць наступны вузел у часовай зменнай, як наступны
      • Змяніце кірунак паказальніка з дапамогай head.next = папярэдняя
      • prev = кіраўнік
      • Рухайцеся наперад у спісе, выкарыстоўваючы галава = наступны
    • вяртаць Папярэдняя
  4. Зараз, напішыце два паказальнікі ptr1 і ptr2 перабіраць абедзве паловы:
    1. ptr1 = галава
    2. ptr2 = старт другой паловы
    3. у той час як ptr2 не роўна нулю:
      1. if ptr1.значэнне не роўна ptr2.значэнне
        1. вяртаць ілжывы
    4. вяртаць праўда як мы правяралі кожны вузел у першай і другой палове
  5. Раздрукуйце вынік

Рэалізацыя рашэння Leetcode са звязаным спісам Palindrome

Праграма C ++

#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;
}

Праграма Java

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

Аналіз складанасці рашэння з выкарыстаннем спісу палітромаў з выкарыстаннем штрых-кода

Складанасць часу

O (N) паколькі мы выкарыстоўваем лінейныя завесы, каб знайсці сярэдзіну спіса, перавярнуць яго назад і параўнаць абедзве паловы. Вось, N = памер спісу.

Касмічная складанасць

O (1) бо мы выкарыстоўваем толькі пастаянную дадатковую прастору.