Palindrome Linked List

 

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)