Check if the given Linked List is Palindrome

In this article, we will solve the problem of determining if a given linked list is a palindrome. Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example:

Input: 1 -> 1 -> 1 -> 1

Output: true

Input: 1 -> 2 -> 3

Output: false

Solution:

To determine if a linked list is a palindrome, we can follow these steps:

1.    Find the Middle of the Linked List:

o   Use the slow and fast pointer technique to find the middle node of the linked list.

2.    Reverse the Second Half of the Linked List:

o   Reverse the second half of the linked list starting from the middle node.

3.    Compare the Two Halves:

o   Compare the first half and the reversed second half of the linked list.

Time Complexity: O(N)

Space Complexity: O(1)