234. Palindrome Linked List

class Solution { public: ListNode* reverse(ListNode* head){ if (head==nullptr || head->next == nullptr) return head; ListNode* newhead = reverse(head->next); ListNode* ptr = newhead; while(ptr->next!=nullptr) ptr = ptr->next; ptr->next = head; head->next = nullptr; return newhead; } bool isPalindrome(ListNode* head) { if (head==nullptr || head->next == nullptr) return true; ListNode* slow, *fast; slow = head; fast = head->next; while(fast!=nullptr && fast->next!=nullptr){ slow = slow->next; fast = fast->next->next; } // odd or even number of nodes, both reverse slow->next. Use the second part to check stopping condition of while loop ListNode* second = reverse(slow->next); // compare first and second half ListNode* first = head; while(second!=nullptr){ if (first->val != second->val) return false; else { first = first->next; second = second->next; } } return true; } };