Cover image for LeetCode Hot 100 P234 Palindrome Linked List

LeetCode Hot 100 P234 Palindrome Linked List

(Updated: )
algorithm
, , ,
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 divide the linked list into two equal halves. Note that the number of nodes may be even or odd. Then reverse the first half.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/**
 * 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);
}