【LBLD】如何判断回文链表
判断回文单链表
/**
* 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) {}
* };
*/
class Solution {
public:
ListNode *left;
bool isPalindrome(ListNode* head) {
left = head;
return traverse(head);
}
bool traverse(ListNode* head) {
if (head == nullptr) return true;
bool res = traverse(head->next);
res = res && (left->val == head->val);
left = left->next;
return res;
}
};
优化空间复杂度
使用快慢指针找到链表中点，然后把链表后半段反转，双指针判断两个链表是否相同。
/**
* 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) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
// 使用快慢指针找到中点
ListNode *slow = head, *fast = head;
while (nullptr != fast && nullptr != fast->next) {
fast = fast->next->next;
slow = slow->next;
}
if (nullptr != fast) {
slow = slow->next;
}
ListNode *left = head;
ListNode *right = reverse(slow);
while (nullptr != right) {
if (right->val != left->val) return false;
left = left->next;
right = right->next;
}
return true;
}
ListNode* reverse(ListNode* head) {
ListNode *pre = nullptr;
ListNode *cur = head;
ListNode *nxt = head;
while (cur) {
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};