ການແກ້ໄຂບັນຊີລາຍຊື່ທີ່ມີການເຊື່ອມໂຍງຂອງ Palindrome


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg Capital One Cisco ເຟສບຸກ ກູໂກ Grab Intel IXL Microsoft Nutanix Oracle Paytm SnapChat Uber Yandex
ບັນຊີທີ່ເຊື່ອມໂຍງ ສອງຈຸດ

ໃນບັນຫາ "ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ Palindrome", ພວກເຮົາຕ້ອງກວດເບິ່ງວ່າມີຕົວເລກທີ່ສົມບູນແບບຢ່າງສົມຄວນ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ ແມ່ນ palindrome ຫຼືບໍ່.

ຍົກຕົວຢ່າງ

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

ຄຳ ອະທິບາຍ # 1: ບັນຊີລາຍຊື່ແມ່ນ palindrome ເພາະວ່າທຸກໆອົງປະກອບຕັ້ງແຕ່ເລີ່ມຕົ້ນແລະດ້ານຫຼັງແມ່ນມີຄຸນຄ່າຄືກັນ.

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

ຄຳ ອະທິບາຍ # 2: ບັນຊີລາຍຊື່ບໍ່ແມ່ນ palindrome ເພາະວ່າອົງປະກອບຈາກດ້ານຫລັງແລະດ້ານຂ້າງບໍ່ຄືກັນ.

ວິທີການ (Recursion)

ນີ້ງ່າຍທີ່ຈະສັງເກດເຫັນວ່າພວກເຮົາຕ້ອງມີລາຍລະອຽດຂອງຂໍ້ມູນຈາກທາງຫລັງຂອງແຖວເພື່ອກວດສອບຄຸນສົມບັດຂອງ palindrome. ໃນກໍລະນີນີ້, ພວກເຮົາມີ ຢ່າງໂສດ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງມີຄວາມຫມາຍວ່າພວກເຮົາພຽງແຕ່ສາມາດກ້າວໄປຂ້າງ ໜ້າ ເພື່ອສາມາດບັນລຸຂໍ້ໄດ້. ດັ່ງນັ້ນ, ມັນຈຶ່ງກາຍເປັນສິ່ງ ສຳ ຄັນທີ່ຈະ ນຳ ໃຊ້ໂຄງສ້າງຂໍ້ມູນ ຈຳ ນວນ ໜຶ່ງ ເພື່ອຈັບຂໍ້ທີ່ຢູ່ທາງຫຼັງ, ຕົວຢ່າງ stack ແມ່ນທາງເລືອກທີ່ເປັນໄປໄດ້ຍ້ອນວ່າມັນຮັກສາຂໍ້ທີ່ຫຼ້າສຸດຢູ່ເທິງສຸດ. ພວກເຮົາຍັງສາມາດໃຊ້ການເອີ້ນຄືນໄດ້ຄືກັນ. ການເອີ້ນຄືນແມ່ນສະຫງ່າງາມທີ່ຈະໃຫ້ຄຸນຄ່າຂອງໂຫນດຕາມ ລຳ ດັບແບບກົງກັນຂ້າມ. ພິຈາລະນາ pseudocode ທົ່ວໄປຂ້າງລຸ່ມນີ້ເພື່ອຄວາມເຂົ້າໃຈດີຂື້ນ:

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

ລະຫັດຂ້າງເທິງພິມຄັ້ງ ທຳ ອິດ ໄວ້ nodes ໃນຕົ້ນໄມ້ເພາະວ່າພວກເຮົາເອີ້ນຄືນການເຮັດວຽກເພື່ອໄປຫາລູກທີ່ຢູ່ເບື້ອງຊ້າຍຂອງຮາກກ່ອນທີ່ຈະພິມຄ່າຂອງຂໍ້ນັ້ນເອງ. ຄ້າຍຄືກັນ, ພວກເຮົາສາມາດໃຊ້ໄດ້ ການເອີ້ນຄືນ ໄປຫາຂໍ້ສຸດທ້າຍກ່ອນແລະເມື່ອ ໜ້າ ທີ່ຈະເຮັດວຽກກັບຄືນ, ພວກເຮົາຈະໄດ້ຮັບຄ່າ node ຕາມ ລຳ ດັບ. ພວກເຮົາຈະ ນຳ ໃຊ້ຕົວແປໄປຂ້າງ ໜ້າ ເຊິ່ງມັນຈະບໍ່ຖືກຜົນກະທົບຈາກການເອີ້ນຄືນ. ດ້ວຍວິທີນີ້, ພວກເຮົາສາມາດປຽບທຽບມູນຄ່າຂອງຕົວປ່ຽນແປງແລະມູນຄ່າຂອງຂໍ້ຕໍ່ໄດ້ຮັບໂດຍການເອີ້ນຄືນເພື່ອປຽບທຽບອົງປະກອບ.

ລະບົບວິເຄາະ

  1. ໜ້າ ທີ່ isPalindrome () ຖືກນໍາໃຊ້ເພື່ອກັບຄືນບໍ່ວ່າບັນຊີລາຍຊື່ກັບ ຫົວຫນ້າ ແມ່ນ palindrome ຫຼືບໍ່
  2. ພວກເຮົາປະກາດສະມາຊິກຂໍ້ມູນຂອງຊັ້ນຮຽນທີ່ມີຊື່ ຫນ້າ ການເກັບຮັກສາຂໍ້ຂໍ້ມູນ ສຳ ລັບການສົ່ງຕໍ່
  3. In isPalindrom ():
    • ເລີ່ມຕົ້ນ ໜ້າ = ຫົວ
    • ກັບຄືນ palindromeCheck (ຫົວ)
  4. In palindromeCheck (ໃນປະຈຸບັນ):
    • If ໃນປະຈຸບັນ is null:
      • ການກັບຄືນມາ ທີ່ແທ້ຈິງ
    • If palindromeCheck (current.next) is ທີ່ບໍ່ຖືກຕ້ອງ:
      • ການກັບຄືນມາ ທີ່ບໍ່ຖືກຕ້ອງ
    • If current.value is ບໍ່ ເທົ່າ​ທຽມ​ກັນ​ກັບ front.value
      • ການກັບຄືນມາ ທີ່ບໍ່ຖືກຕ້ອງ
    • ທາງ ໜ້າ ເພີ່ມຂື້ນເປັນ:
      • ໜ້າ = front.next
    • ການກັບຄືນມາ ທີ່ແທ້ຈິງ ດັ່ງທີ່ພວກເຮົາປະຕິບັດການກວດສອບທັງ ໝົດ
  5. ພິມຜົນໄດ້ຮັບ

ການປະຕິບັດຂອງ Palindrome ບັນຊີລາຍຊື່ເຊື່ອມໂຍງ Leetcode Solution

ໂຄງການ 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

ການວິເຄາະຄວາມສັບສົນຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ Palindrome Leetcode

ຄວາມສັບສົນເວລາ

ໂອ (N) ດັ່ງທີ່ພວກເຮົາຮວບຮວມບັນຊີລາຍຊື່ການນໍາໃຊ້ recursion. ນີ້, N = ຈຳ ນວນຂໍ້ມູນໃນບັນຊີ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N) ດັ່ງທີ່ພວກເຮົາເອີ້ນຟັງຊັນທີ່ເອີ້ນຫາເພື່ອກວດສອບທຸກໆການສ້າງ node N stack ເຟຣມໃນຫນ່ວຍຄວາມ ຈຳ.

ວິທີການ (ປີ້ນກັບກັນອີກເຄິ່ງ ໜຶ່ງ)

ວິທີດຽວທີ່ຈະ ກຳ ຈັດພື້ນທີ່ທີ່ໃຊ້ໃນການຄົ້ນຫາຄືນ ໃໝ່ ແມ່ນການດັດແປງລາຍການທີ່ຢູ່ໃນສະຖານທີ່. ພວກເຮົາປີ້ນກັບກັນໃນເຄິ່ງທີ່ສອງຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະຫຼັງຈາກນັ້ນໃຊ້ສອງທິດທາງສົ່ງຕໍ່ ສຳ ລັບທັງສອງຂ້າງເພື່ອກວດເບິ່ງວ່າມູນຄ່າທີ່ສອດຄ້ອງກັນຈະເທົ່າກັນ. ສຳ ລັບຂະບວນການນີ້, ພວກເຮົາຕ້ອງການ:

  • ຊອກຫາເຄິ່ງກາງຂອງບັນຊີລາຍການດັ່ງນັ້ນພວກເຮົາສາມາດປີ້ນກັບກັນໃນເຄິ່ງທີ່ສອງ.
  • ສ້າງ ໜ້າ ທີ່ເພື່ອປ່ຽນເຄິ່ງ ໜຶ່ງ ຂອງລາຍການ
  • ກວດເບິ່ງວ່າເຄິ່ງ ທຳ ອິດແລະເຄິ່ງທີສອງແມ່ນເທົ່າກັນບໍ

ທັງ ໝົດ ທີ່ກ່າວມາຂ້າງເທິງນີ້ສາມາດເຮັດໄດ້ຕາມເວລາເສັ້ນ. ຫຼັງຈາກທີ່ພວກເຮົາປ່ຽນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງເຂົ້າມາ, ພວກເຮົາເລີ່ມກວດສອບຈົນກ່ວາເຄິ່ງທີ່ສອງ ສຳ ເລັດ.

ການແກ້ໄຂບັນຊີລາຍຊື່ທີ່ມີການເຊື່ອມໂຍງຂອງ Palindrome

ລະບົບວິເຄາະ

  1. If ຫົວຫນ້າ is null:
    • ກັບຄືນມາເປັນຄວາມຈິງ
  2. ຊອກຫາເຄິ່ງກາງຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍໃຊ້ ຄົນກາງ (ຫົວຫນ້າການທໍາງານຂອງ:
    • ເລີ່ມຕົ້ນສອງຈຸດ ຊ້າ ແລະ ໄວ ທັງສອງຊີ້ໄປທີ່ຫົວຂອງບັນຊີ
    • ຈົນກ່ວາ fast.next ແລະ fast.next.next ແມ່ນທັງສອງ ບໍ່ ບໍ່ມີ:
      1. ເພີ່ມຂຶ້ນ ຊ້າ ຮອດປີ 1, slow = slow.next
      2. ເພີ່ມຂຶ້ນ ໄວ ຮອດປີ 2, ໄວ = fast.next.next
    • ຊ້າ ຕົວຊີ້ປັດຈຸບັນຊີ້ໃຫ້ເຫັນຢູ່ເຄິ່ງກາງຂອງບັນຊີລາຍການ
    • ການກັບຄືນມາ ຊ້າ
  3. ຕອນນີ້ພວກເຮົາປ່ຽນຄືນເຄິ່ງທີສອງຂອງບັນຊີການໂທ reverseList (ຫົວ = middle.next) ຫນ້າທີ່
    • ຂໍ້ລິເລີ່ມ prev = null
    • ໃນຂະນະທີ່ ຫົວຫນ້າ ບໍ່ແມ່ນ
      • ເກັບຮັກສາ node ຕໍ່ໄປໃນຕົວແປຊົ່ວຄາວ, ຄື ຕໍ່ໄປ
      • ປີ້ນກັບທິດທາງຊີ້ໂດຍໃຊ້ head.next = prev
      • prev = ຫົວ
      • ກ້າວໄປ ໜ້າ ໃນບັນຊີໂດຍໃຊ້ head = ຕໍ່ໄປ
    • ການກັບຄືນມາ prev
  4. ໃນປັດຈຸບັນ, intialise ສອງຊີ້ ptr1 ແລະ ptr2 ກັບ iterate ໂດຍຜ່ານການທັງສອງ halves:
    1. ptr1 = ຫົວ
    2. ptr2 = ເລີ່ມຕົ້ນ ຂອງເຄິ່ງທີ່ສອງ
    3. ໃນຂະນະທີ່ ptr2 ບໍ່ແມ່ນ
      1. if ptr1.ມູນຄ່າ ບໍ່ເທົ່າກັບ ptr2.ມູນຄ່າ
        1. ການກັບຄືນມາ ທີ່ບໍ່ຖືກຕ້ອງ
    4. ການກັບຄືນມາ ທີ່ແທ້ຈິງ ດັ່ງທີ່ພວກເຮົາໄດ້ກວດເບິ່ງທຸກໆຮູດັງໃນເຄິ່ງ ທຳ ອິດແລະສອງ
  5. ພິມຜົນໄດ້ຮັບ

ການປະຕິບັດຂອງ Palindrome ບັນຊີລາຍຊື່ເຊື່ອມໂຍງ Leetcode Solution

ໂຄງການ 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

ການວິເຄາະຄວາມສັບສົນຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ Palindrome Leetcode

ຄວາມສັບສົນເວລາ

ໂອ (N) ໃນຂະນະທີ່ພວກເຮົາໃຊ້ສາຍເສັ້ນເພື່ອຊອກຫາເຄິ່ງກາງຂອງບັນຊີ, ປີ້ນກັບມັນ, ແລະປຽບທຽບກັບທັງສອງຂ້າງ. ທີ່ນີ້, N = ຂະ ໜາດ ຂອງລາຍການ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ພິເສດທີ່ຄົງທີ່ເທົ່ານັ້ນ.