Palindrome Linked List

Implement a function to check if a linked list is a palindrome.

http://www.lintcode.com/en/problem/palindrome-linked-list/

Solution

快慢指针将list分成两段
反转其中一段
比较判断是否为palindrome

class Solution {
public:
    /**
     * @param head a ListNode
     * @return a boolean
     */
    bool isPalindrome(ListNode* head) {
        // Write your code here
        if(head == nullptr) return true;
        ListNode *slow = head;
        ListNode *fast = head;
        ListNode *pre_slow = head;
        //using a pair of fast and slow pointers to figure out the middle of the list
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            pre_slow = slow;
        }
        //reverse the later half
        ListNode *second_half = reverse(slow);
        pre_slow->next = nullptr;
        //check if the first half equals to the second half
        //the first half may be one element less than the second half
        while(head!= nullptr && second_half != nullptr) {
            if(second_half->val != head->val) {
                return false;
            }
            second_half = second_half->next;
            head = head->next;
        }
        return true;
    }
    ListNode *reverse(ListNode *head) {
        if(head == nullptr) return NULL;
        ListNode *pre = NULL;
        ListNode *cur = head;
        while(cur) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};