C++ Code with comments simple to understand.


  • 0
    P

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      class Solution {
      public:
      ListNode
      reverseOfList(ListNode* head)
      {

        ListNode* prev = NULL;
        ListNode* next = NULL;
        while(head)
        {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
            
        }
        head = prev;
        return head;
      

      }

      bool isPalindrome(ListNode* head) {

       ListNode* fastItr = head;
       ListNode* slowItr = head;
       bool isPal = true;
      //find the middle element
       while(fastItr && fastItr->next)
       {
           slowItr = slowItr->next;
           fastItr = fastItr->next->next;
       }
      //now the slow is in the middle. we need to save this location. To reset the list back
       ListNode* moveBack = slowItr;
      // reverse the second half of the list
       ListNode* reverse = reverseOfList(slowItr);
       //reset the list back to start
       fastItr = head;
      
       while(reverse && fastItr)
       {
           //if the values are not same it not a palidrome
           if(reverse->val != fastItr->val)
           {
                isPal = false;
                break;
           }
           reverse = reverse->next;
           fastItr = fastItr->next;
       }
       //get back list to orginal state
       reverseOfList(moveBack);
       return isPal;
      

      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.