leetcode回文链表

leetcode 回文链表

题目

题解

两种方式进行题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 //第一种方式 将链表按照顺序存储再数组中， 然后一个再前面进行遍历， 一个再后面进行遍历，不相等的话就返回false， 完全遍历完了 之后再返回true
// class Solution {
// public:
//     bool isPalindrome(ListNode* head) {
//         if (head == nullptr || head->next == nullptr) return true;
//         vector<int> ans;
//         while (head) {
//             ans.push_back(head->val);
//             head= head->next;
//         }
//         for (int i = 0, j = ans.size() - 1; i < j; i++, j--) {
//             if (ans[i] != ans[j]) {
//                 return false;
//             }
//         }
//         return true;
//     }
// };


//第二种方式， 先找到中间位置 ，然后把后面的链表反转过来， 之后在和前面进行比较， 要是不相同的话就返回false， 反之返回true
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return true;

        // Step 1: Find the middle of the linked list using slow and fast pointers
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half of the linked list
        ListNode* prev = nullptr;
        while (slow != nullptr) {
            ListNode* temp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = temp;
        }

        // Step 3: Compare the first and second half nodes
        ListNode* left = head;
        ListNode* right = prev;
        while (right != nullptr) {
            if (left->val != right->val) return false;
            left = left->next;
            right = right->next;
        }

        // (Optional) Step 4: Restore the second half back (if needed)
        // You can implement this part if the problem requires you to keep the original structure.

        return true;
    }
};