palindrome linked list

1#include<bits/stdc++.h>
2 
3using namespace std;
4 
5 
6struct ListNode {
7    int val;
8    ListNode *next;
9    ListNode() : val(0), next(nullptr) {}
10    ListNode(int x) : val(x), next(nullptr) {}
11    ListNode(int x, ListNode *next) : val(x), next(next) {}
12};
13 
14// Function to find the mid of linked-list
15ListNode* find_middle(ListNode* head,int n)
16        {
17            ListNode *slow=head,*fast=head;
18            while(fast!=NULL && fast->next!=NULL)
19            {
20                slow=slow->next;
21                fast=fast->next->next;
22            } 
23            if(n&1)
24                return slow->next;
25            else
26                return slow;
27        }
28// Function to Reverse the List using three pointers
29ListNode* reverse_link(ListNode* head)
30        {
31            ListNode *prev=NULL;
32            ListNode *curr=head;
33            ListNode *next=NULL;
34            while(curr!=NULL)
35            {
36                next=curr->next;
37                curr->next=prev;
38                prev=curr;
39                curr=next;
40            }
41            return prev;
42        }
43// Return if the Linked List is palindrome  
44bool isPalindrome(ListNode* head) {
45        if(head==NULL || head->next==NULL)
46            return true;
47        
48        ListNode *temp=head;
49        // Iterate to count odd/even
50        int n=0;
51        while(temp!=NULL)
52        {
53            temp=temp->next;
54            n++;
55        }
56        temp=head;
57        // Find the mid elemeny
58        ListNode *head_mid=find_middle(temp,n);
59        // Reverse the second half linked-list
60        ListNode *head_rev=reverse_link(head_mid);
61        // Verify first half and second half of linked-list are equivalent
62        while(head_rev!=NULL)
63        { 
64 
65            if(head->val!=head_rev->val)
66                return false;
67            
68            head_rev=head_rev->next;
69            head=head->next;
70        }
71        return true;
72    }
73 
74// Driver Function
75int main(){
76    // Create nodes
77    ListNode one = ListNode(31);
78    ListNode two = ListNode(32);
79    ListNode three = ListNode(33);
80    ListNode four = ListNode(32);
81    ListNode five = ListNode(31);
82 
83    ListNode *one_ptr = &one; 
84    ListNode *two_ptr = &two; 
85    ListNode *three_ptr = &three; 
86    ListNode *four_ptr = &four; 
87    ListNode *five_ptr = &five; 
88 
89    // Connect all the nodes
90    five_ptr->next = NULL;
91    one_ptr->next = &two;
92    two_ptr->next = &three;
93    three_ptr->next = &four;
94    four_ptr->next = &five;
95    ListNode* temp = &one;
96 
97    
98    // Call function to return bool if the list is palindrome or not
99    int result = isPalindrome(&one);
100 
101    if(result == 1)
102            cout<<"The value is Palindrome\n";
103    else
104        cout<<"The value is NOT Palindrome\n";
105 
106return 0;
107}
108 
109

1#include<bits/stdc++.h>
2 
3using namespace std;
4 
5// Declaration of a single Node
6class Node {
7public:
8        int data;
9        Node(int d){
10            data = d;
11        }
12        Node *ptr;
13};
14 
15// Function that returns boolean value
16bool isPalin(Node* head){
17        
18        // Temp pointer
19        Node* slow= head;
20 
21        // Create a stack
22        stack <int> s;
23 
24 
25        // First traversal to push all the elements to stack
26        while(slow != NULL){
27                s.push(slow->data);
28                slow = slow->ptr;
29        }
30 
31        // Second Traversal to compare the stack and node
32        while(head != NULL ){
33            
34            int i=s.top();
35            s.pop();
36 
37            // Compare data
38            if(head -> data != i){
39                return false;
40            }
41        head=head->ptr;
42        }
43 
44return true;
45}
46 
47// Driver Function
48int main(){
49    // Create nodes
50    Node one = Node(31);
51    Node two = Node(32);
52    Node three = Node(33);
53    Node four = Node(34);
54    Node five = Node(35);
55 
56    // Connect all the nodes
57    five.ptr = NULL;
58    one.ptr = &two;
59    two.ptr = &three;
60    three.ptr = &four;
61    four.ptr = &five;
62    Node* temp = &one;
63 
64    
65    // Call function to return bool if the list is palindrome or not
66    int result = isPalin(&one);
67 
68    if(result == 1)
69            cout<<"The value is True\n";
70    else
71        cout<<"The value is False\n";
72 
73return 0;
74}