234. Palindrome Linked List | LeetCode Solution

 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;

  }

};