মডিউল ১১-৫ঃ Palindrome Linked List

প্রবলেম লিংকঃ Palindrome Linked List

প্রবলেম স্টেটমেন্টঃ একটি সিংগলি লিংকড লিস্ট দেওয়া থাকবে। লিংকড লিস্টটি পেলিনড্রোম কিনা তা বলতে হবে। সল্যুশনঃ আমরা টু পয়েন্টার টেকনিক ব্যাবহার করে পেলিনড্রোম চেক করার কথা ভাবতে পারি। কিন্তু যেহেতু এটি একটি সিংগলি লিংকড লিস্ট তাই এখানে আমরা পয়েন্টার কে পেছনে নিয়ে আসতে পারব না। এক্ষেত্রে আমরা যেটা করতে পারি, সিংগলি লিংকড লিস্টকে রিভার্স করে আরেকটি সিংগলি লিংকড লিস্ট এ রেখে দিতে পারি। তারপর চেক করে দেখব এই দুটি সিংগলি লিংকড লিস্ট সেইম কিনা। সেইম হলে পেলিনড্রোম না হলে পেলিনড্রোম না। আমরা সিংগলি লিংকড লিস্ট রিভার্স করা পূর্বের আর্টিকেলে দেখেছি। সেভাবেই আমরা রিভার্স করে ফেলতে পারি।

class Solution
{
public:
    void insert_tail(ListNode *&head, ListNode *&tail, int val)
    {
        ListNode *newNode = new ListNode(val);
        if (head == NULL)
        {
            head = newNode;
            tail = newNode;
            return;
        }
        tail->next = newNode;
        tail = tail->next;
    }
    void reverse(ListNode *&head, ListNode *cur)
    {
        if (cur->next == NULL)
        {
            head = cur;
            return;
        }
        reverse(head, cur->next);
        cur->next->next = cur;
        cur->next = NULL;
    }
    void print_list(ListNode *head)
    {
        ListNode *tmp = head;
        while (tmp != NULL)
        {
            cout << tmp->val << " ";
            tmp = tmp->next;
        }
    }
    bool isPalindrome(ListNode *head)
    {
        ListNode *newHead = NULL;
        ListNode *newTail = NULL;
        ListNode *tmp = head;
        while (tmp != NULL)
        {
            insert_tail(newHead, newTail, tmp->val);
            tmp = tmp->next;
        }
        reverse(newHead, newHead);
        print_list(newHead);
        tmp = head;
        ListNode *tmp2 = newHead;
        while (tmp != NULL)
        {
            if (tmp->val != tmp2->val)
            {
                return false;
            }
            tmp = tmp->next;
            tmp2 = tmp2->next;
        }
        return true;
    }
};