Palindrome Linked List

Problem

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Follow up: Could you do it in O(n) time and O(1) space?

Constraints

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Solution

The problem Palindrome Linked List can be solved in O(n) time and O(1) space by reversing half of the list and comparing elements starting from each end. Starting index of the second half of the list can be found by using 2 pointers, one moving 1 node at a time while the other moving 2 node at a time until the latter reaches the end of the list. In addition, second half of the list can be reversed by utilizing the technique from Reverse Linked List.

Implementation

/**
 * 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:
    bool isPalindrome(ListNode *head)
    {
        ListNode *tortoise = head;
        ListNode *hare = head;

        while (hare->next != NULL && hare->next->next != NULL)
        {
            tortoise = tortoise->next;
            hare = hare->next->next;
        }

        ListNode *cur = tortoise->next;
        ListNode *tail = NULL;
        while (cur != NULL)
        {
            ListNode *next = cur->next;
            cur->next = tail;
            tail = cur;
            cur = next;
        }

        while (tail != NULL)
        {
            if (head->val != tail->val)
                return false;

            head = head->next;
            tail = tail->next;
        }

        return true;
    }
};