【题目】
给定一个链表的头节点head，请判断该链表是否为回文结构。例如：1->2->1，返回true。1->2->2->1，返回true。15->6->15，返回true。1->2->3，返回false。进阶：如果链表长度为N，时间复杂度达到O（N），额外空间复杂度达到O（1）。【题解】方法一：遍历一遍链表，将数据压入栈中然后再遍历一遍链表与栈的弹出数据对比方法二：使用快慢指针，将链表的前部分压入栈，然后栈数据弹出与链表的后半部分对比方法三：使用快慢指针，将链表的后半部分反转，然后与链表前半部分对比
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 struct Node 8 { 9 int val; 10 Node* next; 11 Node(int a = 0) :val(a), next(nullptr) {} 12 }; 13 14 bool Way1(Node* head) 15 { 16 stack s; 17 Node* p = head->next; 18 while (p) 19 { 20 s.push(p->val); 21 p = p->next; 22 } 23 p = head->next; 24 while (!s.empty()) 25 { 26 if (p->val != s.top()) 27 return false; 28 p = p->next; 29 s.pop(); 30 } 31 return true; 32 } 33 bool Way2(Node* head) 34 { 35 Node *p, *q; 36 stack s; 37 p = q = head->next; 38 while (q && q->next) 39 { 40 p = p->next; 41 q = q->next->next; 42 } 43 if (q) 44 p = p->next; 45 while (p) 46 { 47 s.push(p->val); 48 p = p->next; 49 } 50 p = head->next; 51 while (!s.empty()) 52 { 53 if (p->val != s.top()) 54 return false; 55 p = p->next; 56 s.pop(); 57 } 58 return true; 59 } 60 bool Way3(Node* head) 61 { 62 Node *p, *q, *pre=nullptr; 63 stack s; 64 p = q = head->next; 65 while (q && q->next) 66 { 67 pre = p; 68 p = p->next; 69 q = q->next->next; 70 } 71 if (q) 72 { 73 pre = p; 74 p = p->next; 75 } 76 pre->next = nullptr; 77 while (p) 78 { 79 q = p->next; 80 p->next = pre->next; 81 pre->next = p; 82 p = q; 83 } 84 p = head->next; 85 while (pre->next) 86 { 87 if (p->val != pre->next->val) 88 return false; 89 p = p->next; 90 pre = pre->next; 91 } 92 return true; 93 } 94 95 int main() 96 { 97 Node* head = new Node(-1); 98 Node* p = head; 99 vector v;100 v = { 1,2,2,1 };101 for (auto a : v)102 {103 Node* q = new Node(a);104 p->next = q;105 p = q;106 }107 cout << Way1(head) << endl;108 cout << Way2(head) << endl;109 cout << Way3(head) << endl;110 111 return 0;112 }