9 - Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
Solution 1：reverse integer
bool isPalindrome(int x)
{
if(x<)return false;
if(x==reverse(x))
return true;
else
return false;
}
int reverse(int x)
{
long long result=;
while(x!=)
{
result=result*+x%;
x/=;
if(result>INT_MAX)return ;
}
return result;
}
Solution 2 ：Integer to String
#include<string>
#include<sstream>
using namespace std;
bool isPalindrome(int x) {
stringstream ss;
ss<<x;
string str=ss.str(); //string s=to_string(x);
for(int i=,j=str.size()-;i<j;i++,j--){
if(str[i]!=str[j])return false;
}
return true;
}
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?
#include<iostream>
#include<vector>
using namespace std; typedef struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
}node; node* create()
{
node *head=new node(-);
node *temp=head;
int x;
while(cin>>x)
{
node *p=new node(x);
temp->next=p;
temp=temp->next;
}
head=head->next;
temp->next=NULL;
return head;
}
//===============================================================
bool isPalindrome1(node *head)
{
/*Runtime:28ms
tranverse once, put val into vector then judge*/
if(!head)return true;
vector<int> vec;
while(head)
{
vec.push_back(head->val);
head=head->next;
}
int length=vec.size();
for(int i=,j=vec.size()-;i<j;i++,j--){
if(vec[i]!=vec[j])
return false;
}
return true;
}
//===============================================================
node* getMid(node *head)
{
ListNode *slow=head,*fast=head;
while(fast->next && fast->next->next)
{
slow=slow->next;
fast=fast->next->next;
}
if(fast->next)slow=slow->next;
return slow;
}
node* reverse(node *head)
{
if(!head || !head->next)return head;
node *p=head,*cur=p->next;
while(cur)
{
node *post=cur->next;
cur->next=p;
p=cur;
cur=post;
}
head->next=NULL;
return p;
}
bool isPalindrome2(node *head)//Runtime:28ms，拆分逆转后半链表，再同时遍历两链表
{
if(!head)return true;
node *mid=getMid(head);
node *remid=reverse(mid);
while(head && remid){
if(head->val != remid->val)return false;
head=head->next;
remid=remid->next;
}
return true;
}
int main()
{
node *head=create();
cout<<isPalindrome2(head);
system("pause");
}
206 - Reverse Linked List
Reverse a singly linked list.
Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution 1:iteration
such as funtion: node* reverse(node *head) in previous title
Solution 2:recursion
class Solution {
public:
ListNode* reverseList(ListNode* head) { //runtime:8ms
if(head==NULL||head->next==NULL)return head;
ListNode* p = head->next;
ListNode* n = reverseList(p);
head->next = NULL;
p->next = head;
return n;
}
};