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 pointersListNode *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 listListNode* prev = nullptr;while (slow != nullptr) {ListNode* temp = slow->next;slow->next = prev;prev = slow;slow = temp;}// Step 3: Compare the first and second half nodesListNode* 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;}
};