Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
分析：题意为判断单链表是否为回文的。
思路：首先想到的是 遍历一次单链表，将其元素装入vector，然后进行第二次遍历比较来判断回文。
/**
* 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) {
vector<int> temp;
while(head){
temp.push_back(head->val);
head=head->next;
}
for(int i=0,j=temp.size()-1;i<j;i++,j--){
if(temp[i]!=temp[j]) return false;
}
return true;
}
};
可是这种方法：时间复杂度O(n)，空间复杂度O(n)；
为了使空间复杂度为O(1)，可以不采用vector等，思路：找到单链表的中点，进行拆分，逆转后半个链表，然后对这两个链表同时顺序遍历一次进行判断。
/**
* 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 == NULL || head->next == NULL)
return true;
ListNode* mid = getMid(head);
ListNode* head2 = reverse(mid);
while(head && head2)
{
if(head->val != head2->val)
return false;
head = head->next;
head2 = head2->next;
}
return true;
}
ListNode* getMid(ListNode* head)
{// at least two nodes
ListNode* slow = head;
ListNode* fast = head;
ListNode* preslow = NULL;
do
{
fast = fast->next;
if(fast)
{
fast = fast->next;
preslow = slow;
slow = slow->next;
}
}while(fast != NULL);
preslow->next = NULL;
return slow;
}
ListNode* reverse(ListNode* head)
{
if(head == NULL || head->next == NULL)
return head;
else if(head->next->next == NULL)
{// two nodes
ListNode* tail = head->next;
head->next = NULL;
tail->next = head;
return tail;
}
else
{
ListNode* pre = head;
ListNode* cur = pre->next;
pre->next = NULL; // set tail
ListNode* post = cur->next;
while(post)
{
cur->next = pre;
pre = cur;
cur = post;
post = post->next;
}
cur->next = pre;
return cur;
}
}
};
或者：
同样O(n) time and O(1) space c++, fast and slow pointer
class Solution {
public:
bool isPalindrome(ListNode* slow, ListNode* fast)
{
if (fast == nullptr) {
half = slow;
return true;
}
if (fast->next == nullptr) {
half = slow->next;
return true;
}
if (isPalindrome(slow->next, fast->next->next) && slow->val == half->val) {
half = half->next;
return true;
}
return false;
}
bool isPalindrome(ListNode* head) {
return isPalindrome(head, head);
}
ListNode* half;
};