palindrome linked list

Topics

• linked lists
• two pointers technique

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

Idea

We do palindrome validation as follows:

1. Find the middle of the linked list using slow and fast pointers (slow moves 1 step, fast moves 2 steps)
2. Next, we reverse the second half of the list starting from the middle node
3. Finally, compare the first half with the reversed second half using two pointers on different sequences

Time Complexity: $O(n)$
Space Complexity: $O(1)$

The key insight is that reversing the second half allows us to compare nodes symmetrically from both ends without needing extra space for storage.

Code

bool is_palindrome(ListNode *head) {
  // find middle (second middle for even length)
  // reverse second half
  // compare using 2 pointers
 
  if (!head || !head->next) {
    return true;
  }
 
  // find middle
  ListNode *slow = head;
  ListNode *fast = head;
 
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
 
  // reverse second half
  ListNode *prev = nullptr;
  ListNode *curr = slow;
  ListNode *next = nullptr;
 
  while (curr) {
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
 
  // compare using 2 pointers
  ListNode *first = head;
  ListNode *second = prev;
 
  while (second) {
    if (first->val != second->val) {
      return false;
    }
    first = first->next;
    second = second->next;
  }
 
  return true;
}

Related