234. Palindrome Linked List

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?

解题思路: (1)找到中间节点 (2)中间节点的next指针指向的是后半部分 (3)将后半部分反转，判断与前半部分值是否一样

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)    return true;

        ListNode *fast = head, *slow = head;

        //找到中间节点
        while(fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }

        //slow所指就是中间节点,split为后半部分的头
        ListNode *split = slow->next;
        //将后半部分反转
        while(split->next){
            ListNode *after = split->next;
            //将split插入到slow节点的后面，从而实现后半部分的反转
            split->next = after->next;
            after->next = slow->next;
            slow->next = after;
        }

        split = slow->next;
        while(split){
            if(split->val != head->val)
                return false;
            split = split->next;
            head = head->next;
        }
        return true;
    }
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL)  return true;

        ListNode *slow = head, *fast = head;

        //找到中间节点
        while(fast->next && fast->next->next){
            slow =slow->next;
            fast = fast->next->next;
        }

        ListNode *p = slow->next;
        slow->next = NULL;

        //p是后半部分的起点，反转后半部分
        ListNode *newHead = NULL;
        while(p){
            ListNode *temp = p->next;

            p->next = newHead;
            newHead = p;

            p = temp;
        }

        //判断是否为回文
        while(newHead){
            if(newHead->val != head->val)
                return false;

            newHead = newHead->next;
            head = head->next;
        }
        return true;
    }
};