LeetCode Hot 100 P234 Palindrome Linked List

---

Timeline

Timeline

2026-03-13

init

Reverse linked list + fast and slow pointers

---

Problem:

P234 Palindrome Linked List

https://leetcode.cn/problems/palindrome-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

Use fast and slow pointers to split the linked list into two equal parts; note that the cases for even and odd numbers of nodes are different. Then reverse the front part of the linked list.

/**
 * 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) {}
 * };
 */

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)
        {
        }
};

class Solution {
    public:
        bool isPalindrome(ListNode *head)
        {
                if (head == nullptr)
                        return false;
                if (head->next == nullptr)
                        return true;

                ListNode *low = head, *fast = head, *left, *right;
                int cnt = 1;
                // Fast and slow pointers
                while (fast->next != nullptr) {
                        if (low->next)
                                low = low->next;

                        if (fast->next) {
                                fast = fast->next;
                                cnt++;
                        }

                        if (fast->next) {
                                fast = fast->next;
                                cnt++;
                        }
                }

                // 1 2 3 1 low->3 fast->1
                // 1 2 1   low->2 fast->1
                // split to [head, low), [low, fast](偶数, 奇数要舍弃low)

                // revserse [head, low)
                ListNode *prev = head, *p = head->next;
                ListNode *next;
                while (p && p != low) {
                        next = p->next; // store the next
                        p->next = prev;
                        prev = p;
                        p = next; // restore the next
                }
                head->next = nullptr;

                left = prev;

                if (cnt % 2 == 0)
                        right = low;
                else
                        right = low->next;

                // Compare
                while (left && right && left->val == right->val) {
                        left = left->next;
                        right = right->next;
                }

                if (left == nullptr && right == nullptr)
                        return true;

                return false;
        }
};

#include <vector>
using std::vector;

int main()
{
        vector<int> vec = { 1, 2, 3, 4 };
        ListNode *head = nullptr, *tail = nullptr;
        for (int val : vec) { // Tail insertion method
                if (head == nullptr && tail == nullptr) {
                        head = tail = new ListNode(val);
                } else {
                        tail->next = new ListNode(val);
                        tail = tail->next;
                }
        }
        Solution S;
        S.isPalindrome(head);
}