题目

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?

思路

利用双指针法找到链表中点位置，链表中点以后的的元素（不包括中点元素）翻转，再跟链表中点位置以前的元素一一匹配。

代码

/*---------------------------------------
*   日期：2015-07-18
*   作者：SJF0115
*   题目: 234.Palindrome Linked List
*   网址：https://leetcode.com/problems/palindrome-linked-list/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr){
            return true;
        }//if
        // 中点位置
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }//while
        slow = slow->next;
        // 翻转
        ListNode* q = ReverseList(slow);
        // 判断是否是回文串
        ListNode* p = head;
        while(p && q){
            if(p->val != q->val){
                return false;
            }//if
            p = p->next;
            q = q->next;
        }//while
        return true;
    }
private:
    // 翻转
    ListNode* ReverseList(ListNode* head){
        if(head == nullptr){
            return head;
        }//if
        // 头结点
        ListNode* dummy = new ListNode(-1);
        ListNode* p = head;
        ListNode* nextNode = p->next;
        while(p){
            nextNode = p->next;
            p->next = dummy->next;
            dummy->next = p;
            p = nextNode;
        }//while
        return dummy->next;
    }
};

int main(){
    Solution s;
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(3);
    ListNode* node6 = new ListNode(2);
    ListNode* node7 = new ListNode(1);
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node6;
    node6->next = node7;

    bool result = s.isPalindrome(head);
    if(result){
        cout<<"是回文串"<<endl;
    }//if
    else{
        cout<<"不是回文串"<<endl;
    }//else
    return 0;
}

运行时间