Palindrome Linked List #LeetCode

Problem Reference:
https://leetcode.com/problems/palindrome-linked-list/

Problem Statement:
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?

Solution:
Reverse the second half. And compare two halves.

/** * 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* slow = head; ListNode* fast = head; // find center while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } // cut in the middle ListNode* secondHalf = slow->next; slow->next = NULL; // reverse second half ListNode* p = secondHalf; ListNode* reversedSecondHalf = NULL; while(p) { ListNode * current = p; p = p->next; current->next = reversedSecondHalf; reversedSecondHalf = current; } // compare two halves. // The middle node is present when n = 2k + 1. // It will be in the second half and will be skipped because of the condition (list1 && list2) ListNode* list1 = head; ListNode* list2 = reversedSecondHalf; while(list1 && list2) { if (list1->val != list2->val) { return false; } list1 = list1->next; list2 = list2->next; } return true; } };