程序员面试金典——2.7回文链表

Solution1：我的答案

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Palindrome { public: bool isPalindrome(ListNode* pHead) { // write code here if(pHead == NULL) return false; vector<int> res; struct ListNode* cur = pHead; while(cur != NULL) { res.push_back(cur->val); cur = cur->next; } int i = 0, j = res.size() - 1; while(i <= j) { if(res[i] != res[j]) return false; i++; j--; } return true; } };

Solution2：

参考网址：https://www.nowcoder.com/profile/6520332/codeBookDetail?submissionId=13854901 思路：利用快慢指针，找到中间节点；将慢指针节点的值压入栈，到达中间节点后，依次出栈与后续节点的值比较。特别注意长度奇偶数。 【重点】学习利用双指针找链表的中点

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Palindrome { public: bool isPalindrome(ListNode* pHead) { // write code here if(pHead == NULL) return true; stack<int> ss; //利用两个指针走到中间的数这个值得学习啊~ ListNode* p = pHead， *q = pHead; ss.push(p->val); while(q->next != NULL && q->next->next != NULL) { p = p->next; ss.push(p->val); q = q->next->next; } if(q->next == NULL) //长度为奇数 ss.pop(); p = p->next; while(!ss.empty()) { if(ss.top() != p->val) break; p = p->next; ss.pop(); } if(ss.empty()) return true; else return false; } };