234. Palindrome Linked List

Description

Given the head of a singly linked list, determine if it is a palindrome. A linked list is a palindrome if the sequence of values read from the head to the end is the same as the sequence read from the end to the head.

Intuition

A linked list can be considered a palindrome if it reads the same forward and backward. To check this, we can split the list into two halves, reverse the second half, and then compare both halves. If they match, the list is a palindrome.

Approach

1. Find the Middle of the Linked List: - Use two pointers, slow and fast. slow moves one step at a time, while fast moves two steps at a time. By the time fast reaches the end of the list, slow will be at the middle.
2. Reverse the Second Half of the Linked List: - Starting from the middle, reverse the second half of the list. This allows us to compare the first half with the reversed second half directly.
3. Compare the Two Halves: - Compare the values of the nodes in the first half and the reversed second half. If all the values match, the linked list is a palindrome.
4. Restore the List (Optional): - If needed, reverse the second half again to restore the original list structure.

Complexity

Time Complexity:

O(n)

• We traverse the list to find the middle (O(n/2)), reverse the second half (O(n/2)), and then compare the two halves (O(n/2)).

Space Complexity:

O(1)

• The algorithm only uses a constant amount of extra space for pointers and variables.

Code

C++

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 of the linked list
        ListNode* prev = nullptr;
        ListNode* curr = slow;
        
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Compare the first half and the reversed second half
        ListNode* firstHalf = head;
        ListNode* secondHalf = prev;
        
        while (secondHalf != nullptr) {
            if (firstHalf->val != secondHalf->val) {
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }

        return true;
    }
};

Python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        string1 = string2 = ""
        node = head
        
        while node is not None:
            string1 += str(node.val)
            string2 = str(node.val) + string2
            node = node.next
            
        return string1 == string2

Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        // Step 1: Find the middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Step 2: Reverse the second half of the linked list
        ListNode prev = null;
        ListNode curr = slow;
        
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // Step 3: Compare the first half and the reversed second half
        ListNode firstHalf = head;
        ListNode secondHalf = prev;
        
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        
        return true;
    }
}

JavaScript

var isPalindrome = function(head) {
      let string1 = string2 = "";
  let node = head;
  
    while(node != null){
        string1 = `${string1}${node.val}`;
        string2 = `${node.val}${string2}`;
        node = node.next;
    }
    return string1 === string2;
};