Leetcode: 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. find the middle node first, note that

    1   2   3   4 

    1   2   3   4   5

    the middle node for above cases are 2 and 3, respectively. Using two pointers method to find the middle node:

              ListNode *mid = head, *last = head;

              //locate the mid node

              while (last != NULL && last->next != NULL){

                     last = last->next->next;

                     if (last != NULL)mid = mid->next;

              }

2. reverse all the nodes after the middle node. Check here for how to reverse all nodes!

3. check the palindrome with two pointers both in forward direction. 

///////////////////////////////////////////////

//code

class Solution {

public:

       bool isPalindrome(ListNode* head) {

              //check input

              if (head == NULL || head->next == NULL)return true;

              ListNode *mid = head, *last = head;

              //locate the mid node

              while (last != NULL && last->next != NULL){

                     last = last->next->next;

                     if (last != NULL)mid = mid->next;

              }

              //reverse all nodes after mid node

              ListNode *cur = mid->next, *pre = cur->next;

              cur->next = NULL;

              while (pre != NULL){

                     ListNode *tmp = pre->next;

                     pre->next = cur;

                     cur = pre;

                     pre = tmp;

              }

              mid->next = cur;

              //CHECK with two pointers, both forward

              mid = mid->next;

              last = head;

              while (mid != NULL){

                     if (last->val != mid->val)return false;

                     else {

                           last = last->next;

                           mid = mid->next;

                     }

              }

              return true;

       }

};