LeetCode *** 234. Palindrome Linked List

本文主要是介绍LeetCode *** 234. Palindrome Linked List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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?

分析：

如果要得到一个在中间的值，可以考虑一个走一步，一个走两步。

代码：

O（n）space

/*** 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;vector<int> detail;while(head){detail.push_back(head->val);head=head->next;}int len=detail.size();for(int i=0;i<len/2;++i){if(detail[i]!=detail[len-1-i])return false;}return true;}
};

O（1）space

/*** 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 *fast=head,*slow=head;while(fast->next!=NULL&&fast->next->next!=NULL){slow=slow->next;fast=fast->next->next;}slow=reverse(slow->next);while(slow!=NULL){if(head->val!=slow->val)return false;head=head->next;slow=slow->next;}return true;}ListNode *reverse(ListNode *head){ListNode *res=NULL;ListNode *tmp=NULL;while(head!=NULL){tmp=head->next;head->next=res;res=head;head=tmp;}return res;}
};

这篇关于LeetCode *** 234. Palindrome Linked List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---