Palindrome Linked List Leetcode โซลูชัน  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน แอปเปิล บลูมเบิร์ก ทุนหนึ่ง ซิสโก้ Facebook Google คว้า อินเทล IXL ไมโครซอฟท์ Nutanix คำพยากรณ์ Paytm Snapchat Uber Yandex
อัลกอริทึม การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions รายการที่เชื่อมโยง สองตัวชี้

ในปัญหา“ Palindrome Linked List” เราต้องตรวจสอบว่ามีจำนวนเต็มเดี่ยวหรือไม่ รายการที่เชื่อมโยง เป็นพาลินโดรมหรือไม่

ตัวอย่าง  

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

คำอธิบาย # 1: รายการนี้เป็น palindrome เนื่องจากองค์ประกอบทั้งหมดตั้งแต่เริ่มต้นและย้อนกลับมีค่าเท่ากัน

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

คำอธิบาย # 2: รายการไม่ใช่ palindrome เนื่องจากองค์ประกอบจากไปมาไม่เหมือนกัน

แนวทาง (Recursion 

สังเกตได้ง่ายว่าเราจำเป็นต้องมีรายละเอียดของโหนดจากด้านหลังของอาร์เรย์เพื่อตรวจสอบคุณสมบัติของพาลินโดรม ในกรณีนี้เรามีไฟล์ เดี่ยว ๆ รายการที่เชื่อมโยงหมายความว่าเราสามารถทำซ้ำไปข้างหน้าเพื่อไปยังโหนดใดก็ได้ ดังนั้นจึงเป็นเรื่องสำคัญที่จะต้องใช้โครงสร้างข้อมูลเพื่อยึดโหนดจากด้านหลังเช่น กอง เป็นตัวเลือกที่เป็นไปได้เนื่องจากจะทำให้โหนดล่าสุดอยู่ด้านบนสุด นอกจากนี้เรายังสามารถใช้การเรียกซ้ำได้ในทำนองเดียวกัน การเรียกซ้ำเป็นสิ่งที่สวยงามในการรับค่าโหนดในลำดับย้อนกลับ พิจารณารหัสเทียมทั่วไปด้านล่างเพื่อความเข้าใจที่ดีขึ้น:

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

รหัสด้านบนจะพิมพ์ครั้งแรก ซ้าย โหนดในทรีเนื่องจากเราเรียกใช้ฟังก์ชันซ้ำเพื่อไปยังลูกด้านซ้ายของรูทใด ๆ ก่อนที่จะพิมพ์ค่าของโหนดนั้นเอง ในทำนองเดียวกันเราสามารถใช้ การเรียกซ้ำ เพื่อไปยังโหนดสุดท้ายก่อนและเมื่อฟังก์ชันย้อนกลับเราจะได้รับค่าโหนดในลำดับย้อนกลับ เราจะใช้ตัวแปรเพื่อทำซ้ำไปข้างหน้าซึ่งจะไม่ได้รับผลกระทบจากการเรียกซ้ำ ด้วยวิธีนี้เราสามารถเปรียบเทียบค่าของตัววนซ้ำไปข้างหน้าและค่าของโหนดย้อนกลับที่ได้รับจากการเรียกซ้ำเพื่อเปรียบเทียบองค์ประกอบ

ดูสิ่งนี้ด้วย
การกำหนดที่อยู่ IP โซลูชัน Leetcode

ขั้นตอนวิธี

  1. ฟังก์ชั่น isPalindrome () ใช้เพื่อส่งกลับรายการที่มี หัว เป็น palindrome หรือไม่
  2. เราประกาศสมาชิกข้อมูลของคลาสที่ชื่อ ด้านหน้า เพื่อจัดเก็บโหนดสำหรับการทำซ้ำไปข้างหน้า
  3. In isPalindrom ():
    • เริ่มต้น ด้านหน้า = หัว
    • ส่งคืน palindromeCheck (หัว)
  4. In palindromeCheck (ปัจจุบัน):
    • If ปัจจุบัน is โมฆะ:
      • กลับ จริง
    • If palindromeCheck (ปัจจุบัน.ถัดไป) is เท็จ:
      • กลับ เท็จ
    • If ปัจจุบัน.value is ไม่ เท่ากับ front.value
      • กลับ เท็จ
    • ส่วนเพิ่มด้านหน้าเป็น:
      • ด้านหน้า = front.next
    • กลับ จริง ในขณะที่เราทำการตรวจสอบทั้งหมด
  5. พิมพ์ผลลัพธ์

การใช้งาน Palindrome Linked List 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 Linked List Leetcode Solution

ความซับซ้อนของเวลา

บน) เมื่อเราสำรวจรายการเมื่อใช้การเรียกซ้ำ ที่นี่ N = จำนวนโหนดในรายการ

ดูสิ่งนี้ด้วย
Serialize และ Deserialize Binary Tree

ความซับซ้อนของอวกาศ

บน) ในขณะที่เราเรียกใช้ฟังก์ชันวนซ้ำเพื่อตรวจสอบทุกโหนดที่สร้างขึ้น N สแต็กเฟรมในหน่วยความจำ

วิธีการ (ย้อนกลับอีกครึ่งหนึ่ง)  

วิธีเดียวในการกำจัดพื้นที่ที่ใช้ในการเรียกซ้ำคือการแก้ไขรายการที่กำหนดในสถานที่ เราย้อนกลับครึ่งหลังของรายการที่เชื่อมโยงแล้วใช้ตัวทำซ้ำไปข้างหน้าสองตัวสำหรับทั้งสองครึ่งเพื่อตรวจสอบว่าค่าที่ตรงกันนั้นเท่ากัน สำหรับกระบวนการนี้เราจำเป็นต้อง:

  • หาตรงกลางของรายการเพื่อให้เราย้อนกลับครึ่งหลังได้
  • สร้างฟังก์ชันเพื่อย้อนกลับครึ่งหลังของรายการ
  • ตรวจสอบว่าครึ่งแรกและครึ่งหลังเท่ากันหรือไม่

ทั้งหมดข้างต้นสามารถทำได้ในเวลาเชิงเส้น หลังจากที่เราย้อนกลับรายการที่เชื่อมโยงแล้วเราจะเริ่มตรวจสอบจนกว่าครึ่งหลังจะเสร็จสมบูรณ์

Palindrome Linked List Leetcode โซลูชัน

ขั้นตอนวิธี

  1. If หัว is โมฆะ:
    • กลับจริง
  2. ค้นหาตรงกลางของรายการที่เชื่อมโยงโดยใช้ middleOfList (หัวฟังก์ชั่น:
    • เริ่มต้นตัวชี้สองตัว ช้า และ รวดเร็ว ทั้งชี้ไปที่ส่วนหัวของรายการ
    • จนกระทั่ง fast.next และ fast.next.next มีทั้ง ไม่ โมฆะ:
      1. การเพิ่มขึ้น ช้า ภายในปี 1 ช้า = ช้าถัดไป
      2. การเพิ่มขึ้น รวดเร็ว ภายในปี 2 เร็ว = fast.next.next
    • ช้า ตอนนี้ตัวชี้จะชี้ไปที่ตรงกลางของรายการ
    • กลับ ช้า
  3. ตอนนี้เราย้อนกลับครึ่งหลังของการโทรรายการ reverseList (หัว = กลาง.ถัดไป) ฟังก์ชัน
    • เริ่มต้น prev = โมฆะ
    • ในขณะที่ หัว ไม่เป็นโมฆะ:
      • จัดเก็บโหนดถัดไปในตัวแปรชั่วคราวเป็น ถัดไป
      • ย้อนกลับทิศทางตัวชี้โดยใช้ head.next = ก่อนหน้า
      • ก่อนหน้า = หัว
      • เลื่อนไปข้างหน้าในรายการโดยใช้ หัว = ถัดไป
    • กลับ prev
  4. ตอนนี้เริ่มต้นตัวชี้สองตัว ptr1 และ ptr2 เพื่อวนซ้ำทั้งสองครึ่ง:
    1. ptr1 = หัว
    2. ptr2 = เริ่มต้น ของครึ่งหลัง
    3. ในขณะที่ ptr2 ไม่เป็นโมฆะ:
      1. if ptr1.ความคุ้มค่า ไม่เท่ากับ ptr2.ความคุ้มค่า
        1. กลับ เท็จ
    4. กลับ จริง ขณะที่เราตรวจสอบทุกโหนดในครึ่งแรกและครึ่งหลัง
  5. พิมพ์ผลลัพธ์
ดูสิ่งนี้ด้วย
K ช่องว่าง LeetCode

การใช้งาน Palindrome Linked List 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 Linked List Leetcode Solution

ความซับซ้อนของเวลา

บน) เมื่อเราใช้ลูปเชิงเส้นเพื่อค้นหาตรงกลางของรายการให้ย้อนกลับและเปรียบเทียบทั้งสองครึ่ง ที่นี่ N = ขนาดของรายการ

ดูสิ่งนี้ด้วย
การแลกเปลี่ยนขั้นต่ำที่จำเป็นเพื่อนำองค์ประกอบทั้งหมดที่น้อยกว่าหรือเท่ากับ k มารวมกัน

ความซับซ้อนของอวกาศ

O (1) ในขณะที่เราใช้ช่องว่างพิเศษคงที่เท่านั้น