leetcode-234

https://leetcode-cn.com/problems/palindrome-linked-list/

思路:快慢指针

//链表反转
ListNode* reverList(ListNode *head) {
    ListNode* res = nullptr;
    while(head) {
        ListNode *temp = head->next;
        head->next = res;
        res = head;
        head = temp;
    }
    return res;
}
bool isPalindrome(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return true;
    }
    ListNode *slow = head;
    ListNode *faster = head->next;
    ListNode *slowhead = slow;
    while(faster && faster->next) {
        slow = slow->next;
        faster = faster->next->next;
    }
    ListNode *last = slow->next;
    slow->next = nullptr;
    faster = reverList(last);
    while(slowhead && faster) {
        //cout << slowhead->val << " " << faster->val << endl;
        if (slowhead->val != faster->val) {
            return false;
        }
        slowhead = slowhead->next;
        faster = faster->next;
    }
    //cout << slow->val << endl;
    return true;
}

 

上一篇:深度学习实践经验:用Faster R-CNN训练Caltech数据集——修改读写接口


下一篇:POJ - 3069 Saruman‘s Army