题目描述
请判断一个链表是否为回文链表。
样例
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// O(n) 时间复杂度和 O(1) 空间复杂度
bool isPalindrome(ListNode* head) {
if(head == NULL) return true;
// 长度
int len = 0;
ListNode* p = head;
while(p)
{
p = p->next;
len++;
}
// 翻转后半段
int len2;
if(len % 2 == 0) len2 = len / 2;
else len2 = (len + 1) / 2;
p = head;
for(int i = 1; i <= len2; ++i)
p = p->next;
ListNode* b = nullptr; // 从p出开始断开,翻转
while(p)
{
ListNode* tmp = p->next;
p->next = b;
b = p;
p = tmp;
}
// 前后段比较
p = head;
while(b != NULL && p != NULL) // 后半段与前半段比,要么相等,要么短一个长度
{
if(b->val != p->val) return false;
b = b->next;
p = p->next;
}
return true;
}
};