本文共 1302 字，大约阅读时间需要 4 分钟。

/************************************************************************

* Given a singly linked list, determine if it is a palindrome. * * Follow up: * Could you do it in O(n) time and O(1) space? ************************************************************************/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */

class Solution {public:    //find the mid in the List    ListNode* findMid(ListNode* head) {        ListNode *slow=head,*fast=head;         while (fast&&fast->next) {            fast=fast->next->next;            slow=slow->next;        }        return slow;    }    //reverse the hafl List    ListNode* reverse(ListNode* head) {       ListNode *pre=head;ListNode* cur=pre->next;       pre->next=NULL;       while (cur) {           ListNode *nxt=cur->next;           cur->next=pre;           pre=cur;           cur=nxt;       }       return pre;    }    bool isPalindrome(ListNode* head) {        if (head==NULL||head->next==NULL) return true;        ListNode *mid=findMid(head);        ListNode *pre=reverse(mid);        while (pre) {            if (pre->val!=head->val)                return false;            pre=pre->next;            head=head->next;        }        return true;    }};

转载地址：http://apdoi.baihongyu.com/