LeetCode - 234. 回文链表
程序员文章站
2022-04-17 15:52:18
...
234. 回文链表
请判断一个链表是否为回文链表。
解题思路: 先用快慢指针找到链表的中间节点,然后将链表断开,将后半段倒序,然后再判断是否为回文。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode *fast = head, *slow = head, *pre;
while (fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
// cout << pre->val << endl;
}
ListNode *t = pre->next;
pre->next = NULL;
pre = NULL;
while (t) {
ListNode *next = t->next;
t->next = pre;
pre = t;
t = next;
}
while (pre && head) {
if (pre->val != head->val) return false;
pre = pre->next;
head = head->next;
}
return true;
}
};
上一篇: 【LeetCode】234.回文链表
下一篇: LeetCode|234.回文链表