leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0234.cpp (878B)

      1 class Solution {
      2   public:
      3     ListNode *invert(ListNode *head) {
      4         ListNode *p, *q, *r;
      5 
      6         p = head;
      7         q = nullptr;
      8         while (p) {
      9             r = q;
     10             q = p;
     11             p = p->next;
     12             q->next = r;
     13         }
     14         return q;
     15     }
     16 
     17     ListNode *first_half_end(ListNode *head) {
     18         ListNode *fast, *slow;
     19         fast = slow = head;
     20         while (fast->next && fast->next->next) {
     21             fast = fast->next->next;
     22             slow = slow->next;
     23         }
     24         return slow;
     25     }
     26 
     27     bool isPalindrome(ListNode *head) {
     28         if (!head || !head->next) return true;
     29 
     30         ListNode *fhe = first_half_end(head);
     31         ListNode *shs = invert(fhe->next);
     32 
     33         for (ListNode *p = head, *tmp = shs; tmp; p = p->next, tmp = tmp->next)
     34             if (p->val != tmp->val) return false;
     35 
     36         return true;
     37     }
     38 };