时间轴

2026-03-13

init

题目：

P234 回文链表

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

快慢指针把链表分为均等的两部分，注意链表节点为偶数和奇数有不同。然后把前面那部分链表反转。

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;
                // 快慢指针
                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;

                // 比较
                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) { // 尾插法
                if (head == nullptr && tail == nullptr) {
                        head = tail = new ListNode(val);
                } else {
                        tail->next = new ListNode(val);
                        tail = tail->next;
                }
        }
        Solution S;
        S.isPalindrome(head);
}