Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

This problem involves solution to the reverse linked list problem.

Follow up:

Could you do it in O(n) time and O(1) space?

Approach: Reverse the linked list after the middle and see if the first half is equal to the reversed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

/** * 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 == NULL || head->next == NULL){ return true; } ListNode *slow, *fast; slow = head; fast = head; while(fast->next && fast->next->next){ fast = fast->next->next; slow = slow->next; } ListNode *secondHead = slow->next; slow->next = NULL; //reverse second part of the list ListNode *prev = NULL, *curr, *next = secondHead; while(next){ curr = next; next = next->next; curr->next = prev; prev = curr; } //compare two sublists now ListNode *p = curr; ListNode *q = head; while(p){ if(p->val != q->val) return false; p = p->next; q = q->next; } return true; } };