Advertisement
Saleh127

Reverse A Singly LinkedList - Leetcode 234 (palindrome check)

Mar 24th, 2023
752
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution
  12. {
  13. public:
  14.      
  15.     ListNode* mid(ListNode* head)
  16.     {
  17.         ListNode* s=head,*f=head;
  18.         while(f && f->next)
  19.         {
  20.             s=s->next;
  21.             f=f->next;
  22.             if(f) f=f->next;
  23.         }
  24.         return s;
  25.     }
  26.    
  27.    
  28.     ListNode* reverse(ListNode* head)
  29.     {
  30.         ListNode* prev=NULL,*cur=head,*next=NULL;
  31.        
  32.         while(cur)
  33.         {
  34.             next=cur->next;
  35.             cur->next=prev;
  36.             prev=cur;
  37.             cur=next;
  38.         }
  39.        
  40.         cur=prev;
  41.        
  42.         return cur;
  43.     }
  44.    
  45.     bool cmp(ListNode* a,ListNode* b)
  46.     {
  47.         while(a && b)
  48.         {
  49.             if(a->val != b->val) return false;
  50.             a=a->next;
  51.             b=b->next;
  52.         }
  53.         return true;
  54.     }
  55.    
  56.     bool isPalindrome(ListNode* head)
  57.     {
  58.         if(!head || !head->next) return true;
  59.         ListNode* h=head;
  60.         ListNode* m = mid(h);
  61.         ListNode* h1=reverse(m);
  62.         return cmp(head,h1);
  63.     }
  64. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement