234 - Palindrome Linked List

Problem

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

Input: head = [1,2,2,1]
Output: true

Input: head = [1,2]
Output: false

Constraints:

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

Follow-up: do it in O(n) time and O(1) space.

Approach

A palindrome check wants to compare the front against the back, and a singly linked list can only be read forwards. So we using floyd warshall’s algo we use two pointer: slow and fast where fast moves at double speed of slow. This makes slow the middle pointer and we can just reverse the second half the linked list and compare the two linked lists by traversing and comparing.

1 -> 2 -> 3 -> 2 -> 1            slow stops on the middle 3

1 -> 2 -> 3 <- 2 <- 1            reverse from slow; prev is the new head
          |         |
          l walks -> <- r walks

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        while(curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        ListNode* l = head, *r = prev;
        while(r) {
            if(l->val != r->val) {
                return false;
            }
            l = l->next;
            r = r->next;
        }
        return true;
    }
};

• time: O(n) - one pass to the middle, one to reverse, one to compare
• space: O(1) - a handful of pointers, nodes relinked in place