Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

```Input: head = [1,2,2,1]
Output: true
```

Example 2:

```Input: head = [1,2]
Output: false
```

Example 3:

```Input: head = [1,2,3,2,1]
Output: true```

method:

1)Use 'slow'(s) and 'fast'(f) pointers to traverse the list.
2)When 'fast' pointer becomes null, that means the 'slow' pointer is at the middle of the list.
3)reverse the right half of the list from slow pointer(we are reversing right half of the linked list)
4)now keep comparing elements from left half starting from head pointer and right half starting  from slow pointer,
if any element compared is not equal return false
if all are equal return true

c++  implementation :

` bool isPalindrome(ListNode* head) {         ListNode *f=head;         ListNode *s=head;                while(f!=NULL && f->next!=NULL)        {            f=f->next->next;            s=s->next;        }                if(f!=NULL)            s=s->next;                s=reverseList(s);                while(s!=NULL && head!=NULL)        {            if(s->val!=head->val)                return 0;            s=s->next;            head=head->next;        }        return 1;    } ListNode * reverseList(ListNode  *head){ ListNode  *prev=NULL; ListNode* next = NULL; ListNode  *current=head;   while (current != NULL )   {      next = current->next;             // marking next node      current->next = prev;             // reversing link      prev = current;                   // updating prev      current = next;                   // updating current   }   return prev;}`
time complexity:0(n)
space complexity:0(n)

method:

1)Use 'slow'(s) and 'fast'(f) pointers to traverse the list.
2)When 'fast' pointer becomes null, that means the 'slow' pointer is at the middle of the list.
3)reverse the right half of the list from slow pointer(we are reversing right half of the linked list)
4)now keep comparing elements from left half starting from head pointer and right half starting  from slow pointer,
if any element compared is not equal return false
if all are equal return true

c++  implementation :

` bool isPalindrome(ListNode* head) {         ListNode *f=head;         ListNode *s=head;                while(f!=NULL && f->next!=NULL)        {            f=f->next->next;            s=s->next;        }                if(f!=NULL)            s=s->next;                s=reverseList(s);                while(s!=NULL && head!=NULL)        {            if(s->val!=head->val)                return 0;            s=s->next;            head=head->next;        }        return 1;    } ListNode * reverseList(ListNode  *head){ ListNode  *prev=NULL; ListNode* next = NULL; ListNode  *current=head;   while (current != NULL )   {      next = current->next;             // marking next node      current->next = prev;             // reversing link      prev = current;                   // updating prev      current = next;                   // updating current   }   return prev;}`
time complexity:0(n)
space complexity:0(1)
darkmode