面试金典--检查链表是否是回文

题目描述：检查单链表是否是回文。

思路：反转，比较（反转的时候可以借助栈来实现）

 1 #include <iostream>
 2 #include <string>
 3 #include <fstream>
 4 #include <map>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <ctime>
 8 #include <bitset>
 9 #include <stack>
10 
11 using namespace std;
12 
13 template<typename T>
14 class Node
15 {
16 public:
17     Node<T> *next;
18     T data;
19 
20     Node(T d):data(d),next(NULL){}
21     void appendToTail(T d)
22     {
23         Node<T> *end = new Node<T>(d);
24         Node<T> *n = this;
25         while(n->next != NULL)
26         {
27             n = n->next;
28         }
29         n->next = end;
30     }
31 };
32 
33 int main()
34 {
35     //首先判断是否是空以及是否只有一个节点
36     //我这里没实现
37     Node<int> *head = new Node<int>(1);
38     head->appendToTail(2);
39     head->appendToTail(1);
40     Node<int> *headOrg = head;
41     stack<Node<int>*> reverseList;
42     while(head != NULL)
43     {
44         reverseList.push(head);
45         head = head->next;
46     }
47     while(headOrg != NULL && !reverseList.empty())
48     {
49         if(headOrg->data != reverseList.top()->data)
50         {
51             cout<<"false"<<endl;
52             return 0;
53         }
54         else
55         {
56             headOrg = headOrg->next;
57             reverseList.pop();
58         }
59     }
60     cout<<"true"<<endl;
61     return 0;
62 }

其他思路：递归（fun(startNode,len)）,递归的时候返回与当前节点对应的链表尾部的节点。