:给定一个链表,判断它是不是回文链表,根据链表的奇偶分情况,然后反转后半段链表,与前半段比较。
代码:
- struct ListNode {
- int val;
- ListNode * next;
- ListNode(int x) : val(x),
- next(NULL) {}
- };
- class Solution {
- public: bool isPalindrome(ListNode * head) {
- ListNode * slow,
- *fast; //利用快慢指针 slow = fast = head; while (fast && fast->next){ slow = slow->next; fast = fast->next->next; } if (fast){//判断链表的奇偶,奇数就不计中间那个节点 slow->next = reverseList(slow->next); slow = slow->next; } else{//偶数直接反转 slow = reverseList(slow); } while (slow){//判断后半段反转后与前半段是否相等 if (head->val != slow->val){ return false; } slow = slow->next; head = head->next; } return true; } ListNode* reverseList(ListNode* head) {//反转链表 ListNode* newHead = NULL; while (head) { ListNode* nextNode = head->next; head->next = newHead; newHead = head; head = nextNode; } return newHead; }};
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-06/20044711.html