http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/
这里的reverse可以reverse整个list，这样空间需求就是O(n)，不如这个网页写的O(1)的方法
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 #include <map> 9 #include <set> 10 using namespace std; 11 12 struct node { 13 int data; 14 node *next; 15 node() : data(0), next(NULL) { } 16 node(int d) : data(d), next(NULL) { } 17 }; 18 19 void push(node* &head, int k) { 20 node *new_node = new node(k); 21 new_node->next = head; 22 head = new_node; 23 } 24 25 void print(node* head) { 26 while (head) { 27 cout << head->data << " "; 28 head = head->next; 29 } 30 cout << endl; 31 } 32 33 void reverselist(node *&head) { 34 if (!head) return; 35 node *cur = head; 36 node *next = head->next; 37 if (!next) return; 38 reverselist(next); 39 cur->next->next = cur; 40 cur->next = NULL; 41 head = next; 42 } 43 44 bool compare(node *first, node* second) { 45 while (first && second) { 46 if (first->data != second->data) return false; 47 first = first->next; 48 second = second->next; 49 } 50 return first == NULL && second == NULL; 51 } 52 53 bool palin(node *head) { 54 if (!head || !head->next) return true; 55 node *p, *q, *pre; 56 p = q = pre = head; 57 node *midnode = NULL; 58 while (q && q->next) { 59 q = q->next->next; 60 pre = p; 61 p = p->next; 62 } 63 if (q) { //odd number 64 midnode = p; 65 p = p->next; 66 } 67 node *second = p; 68 pre->next = NULL; 69 reverselist(second); 70 bool ans = compare(head, second); 71 reverselist(second); 72 if (midnode) { 73 pre->next = midnode; 74 midnode->next = second; 75 } 76 else pre->next = second; 77 return ans; 78 } 79 80 int main() { 81 node *head = NULL; 82 push(head, 1); 83 push(head, 2); 84 push(head, 3); 85 push(head, 3); 86 push(head, 2); 87 push(head, 1); 88 if (palin(head)) cout << "yes" << endl; 89 else cout << "no" << endl; 90 print(head); 91 return 0; 92 }
recursive的法子很巧
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 #include <map> 9 #include <set> 10 using namespace std; 11 12 struct node { 13 int data; 14 node *next; 15 node() : data(0), next(NULL) { } 16 node(int d) : data(d), next(NULL) { } 17 }; 18 19 void push(node* &head, int k) { 20 node *new_node = new node(k); 21 new_node->next = head; 22 head = new_node; 23 } 24 25 void print(node* head) { 26 while (head) { 27 cout << head->data << " "; 28 head = head->next; 29 } 30 cout << endl; 31 } 32 33 bool palinhelp(node *&left, node *right) { 34 if (right == NULL) return true; 35 bool palin1 = palinhelp(left, right->next); 36 if (!palin1) return false; 37 bool palin2 = right->data == left->data; 38 left = left->next; 39 return palin2; 40 } 41 42 bool palin(node *head) { 43 return palinhelp(head, head); 44 } 45 46 int main() { 47 node *head = NULL; 48 push(head, 1); 49 push(head, 2); 50 push(head, 3); 51 push(head, 3); 52 push(head, 2); 53 push(head, 1); 54 if (palin(head)) cout << "yes" << endl; 55 else cout << "no" << endl; 56 print(head); 57 return 0; 58 }