234. 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
Constraints:
- The number of nodes in the list is in the range
[1, 105]
. 0 <= Node.val <= 9
The solution to the above question is-
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution
{
public:
ListNode *reverse(ListNode *head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *prev = NULL;
ListNode *next = NULL;
while (head != NULL)
{
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
bool isPalindrome(ListNode *head)
{
if (head->next == NULL)
return true;
ListNode *slow = head;
ListNode *fast = head;
while (fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
slow->next = reverse(slow->next);
slow = slow->next;
while (slow != NULL)
{
if (head->val != slow->val)
return false;
slow = slow->next;
head = head->next;
}
return true;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.