Палиндромның байланыстырылған тізімі, парақ кодының шешімі  


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg Capital One Cisco Facebook Google Ұстаңыз Intel IXL Microsoft Нутаниx Oracle Paytm Snapchat қиятын Яндекс
алгоритмдер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions Байланыстырылған тізім Екі нұсқағыш

«Палиндром байланыстырылған тізімі» мәселесінде біз берілген бүтін санды тексеруіміз керек байланыстырылған тізім бұл палиндром немесе жоқ.

мысал  

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

Жоғарыда келтірілген код алдымен басып шығарады сол ағаштағы түйіндер, өйткені біз функцияны түйіннің мәнін басып шығармас бұрын кез-келген түбірдің сол жақ балаларына өту функциясын рекурсивті түрде атаймыз. Сол сияқты, біз де қолдана аламыз рекурсия алдымен соңғы түйіндерге өту үшін және функция кері кеткенде, біз түйін мәндерін кері тәртіпте аламыз. Біз алға жылжу үшін рекурсияға әсер етпейтін айнымалыны қолданамыз. Осылайша, элементтерді салыстыру үшін алға итератор мәні мен рекурсия нәтижесінде алынған кері түйін мәнін салыстыра аламыз.

Сондай-ақ, қараңыз
IP-мекен-жайдың шешім кодын өзгерту

Алгоритм

  1. Функция isPalindrome () тізімі бар-жоғын қайтару үшін қолданылады бас палиндромды немесе жоқ
  2. Біз аталған сыныптың деректер мүшесін жариялаймыз алдыңғы алға қарай қайталау үшін түйіндерді сақтау үшін
  3. In isPalindrom ():
    • Бастамаңыз алдыңғы = бас
    • палиндромды қайтару
  4. In palindromeCheck (ағымдағы):
    • If ағымдағы is NULL:
      • қайтару шынайы
    • If palindromeCheck (ағымдағы.кейінгі) is жалған:
      • қайтару жалған
    • If ағымдағы мән is емес тең алдыңғы.мәні
      • қайтару жалған
    • алдыңғы өсім:
      • алдыңғы = алдыңғы.кейінгі
    • қайтару шынайы өйткені біз барлық тексерулерді жасадық
  5. Нәтижені басып шығарыңыз

Палиндромның байланыстырылған тізімі, Leetcode шешімін енгізу

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

Палиндром байланыстырылған тізімнің Leetcode шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (N) біз рекурсияны пайдаланып тізімді бір рет айналып өткенде. Мұнда, N = тізімдегі түйіндер саны.

Сондай-ақ, қараңыз
Екілік ағашты сериалдау және десериализациялау

Ғарыштың күрделілігі

O (N) біз әр түйінді жасауды тексеру үшін рекурсивті функция деп атаймыз N жадтағы кадрларды жинақтау.

Тәсіл (екінші жартысына кері)  

Рекурсияда қолданылатын кеңістіктен құтылудың жалғыз жолы - берілген тізімді орнында өзгерту. Байланыстырылған тізімнің екінші жартысын артқа айналдырамыз, содан кейін екі жартыға екі алға итераторды қолданып, сәйкес мәндердің тең екендігін тексереміз. Бұл процесс үшін бізге:

  • екінші жартысын кері айналдыру үшін тізімнің ортасын табыңыз.
  • тізімнің екінші жартысын өзгерту функциясын жасаңыз
  • бірінші және екінші жарты тең екенін тексеріңіз

Жоғарыда айтылғандардың барлығын сызықтық уақытта жасауға болады. Байланыстырылған тізімді өзгерткеннен кейін, екінші жартысы аяқталғанша тексере бастаймыз.

Палиндромның байланыстырылған тізімі, парақ кодының шешімітүйреуіш

Алгоритм

  1. If бас is NULL:
    • шындыққа оралу
  2. Байланыстырылған тізімнің ортасын табыңыз middleOfList (басФункциясы:
    • Екі көрсеткішті бастаңыз баяу және жылдам екеуі де тізімнің басын нұсқайды
    • дейін жылдам. келесі және жылдам. келесі екеуі де емес нөл:
      1. Көбею баяу 1 жылға қарай, баяу = баяу.кейінгі
      2. Көбею жылдам 2 жылға қарай, fast = fast.next.next
    • баяу енді көрсеткіш тізімнің ортасын көрсетеді
    • қайтару баяу
  3. Енді біз тізімнің екінші жартысын шақырамыз reverseList (бас = орта.кейінгі) функция
    • Бастау алдыңғы = NULL
    • уақыт бас нөл емес:
      • Келесі түйінді уақытша айнымалы түрінде сақтаңыз Келесі
      • Көмегімен меңзердің бағытын өзгертіңіз head.next = алдыңғы
      • prev = бас
      • Көмегімен тізімде алға жылжыңыз бас = келесі
    • қайтару алдыңғы
  4. Енді екі нұсқағышты іштей анықтаңыз ptr1 және ptr2 екі жартыға дейін қайталану үшін:
    1. ptr1 = бас
    2. ptr2 = бастау екінші жартысы
    3. уақыт ptr2 нөл емес:
      1. if ptr1.құн тең емес ptr2.құн
        1. қайтару жалған
    4. қайтару шынайы біз бірінші және екінші жартыдағы әр түйінді тексердік
  5. Нәтижені басып шығарыңыз
Сондай-ақ, қараңыз
K бос ұяшықтар LeetCode

Палиндромның байланыстырылған тізімі, Leetcode шешімін енгізу

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

Палиндром байланыстырылған тізімнің Leetcode шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (N) сызықтық ілмектерді пайдаланып, тізімнің ортасын тауып, оны кері айналдырып, екі жартысын да салыстырамыз. Мұнда, N = тізім өлшемі.

Сондай-ақ, қараңыз
K-ден кем немесе оған тең барлық элементтерді біріктіру үшін қажетті минималды своптар

Ғарыштың күрделілігі

O (1) өйткені біз тек тұрақты қосымша кеңістікті қолданамыз.

1