algoadvance

Leetcode 234. Palindrome Linked List

Problem Statement

You are given the head of a singly linked list. Return true if it is a palindrome or false otherwise.

Example 1:

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

Example 2:

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

Constraints:

Clarifying Questions

  1. What is the expected output if the input linked list contains only one element?
    • A single-element list is always a palindrome, so the expected output should be true.
  2. Can we use extra space in our solution?
    • The optimal solution should aim for O(1) extra space, but using O(n) space is acceptable initially if it simplifies the implementation.

Strategy

  1. Find the Middle of the Linked List:
    • Use the Floyd’s Tortoise and Hare algorithm to find the middle of the linked list. This requires two pointers: one moves one step at a time (slow), and the other moves two steps at a time (fast).
  2. Reverse the Second Half of the Linked List:
    • Once the middle is found, reverse the second half of the linked list.
  3. Compare Both Halves:
    • Compare the nodes of the first half and the reversed second half. If all corresponding nodes are equal, then the linked list is a palindrome.
  4. Restore the List (Optional):
    • Optionally, restore the second half of the list to its original state if required.

Code

/**
 * 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) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }
        
        // Step 1: Find the middle of the linked list
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Step 2: Reverse the second half
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        
        while (curr != nullptr) {
            ListNode* next_temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next_temp;
        }
        
        // Step 3: Compare the first and second half nodes
        ListNode* first_half = head;
        ListNode* second_half = prev;
        
        while (second_half != nullptr) {
            if (first_half->val != second_half->val) {
                return false;
            }
            first_half = first_half->next;
            second_half = second_half->next;
        }
        
        // Optional Step: Restore the list if necessary
        // reverseList(slow);

        return true;
    }
    
    // Optional: Function to restore the list (if required)
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            ListNode* next_temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next_temp;
        }
        
        return prev;
    }
};

Time Complexity

  1. Finding the Middle: O(n) where n is the number of nodes in the list.
  2. Reversing the Second Half: O(n/2) which simplifies to O(n).
  3. Comparing Both Halves: O(n/2) which simplifies to O(n).

Overall Time Complexity: O(n)

Space Complexity

The algorithm uses a constant amount of extra space (excluding the input space for the linked list).

Overall Space Complexity: O(1)

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI