Skip to main content

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

Python​

First Solution​

  • Time: O(2N)
  • Space: O(N/2)
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        stack = []
        is_even = length % 2 == 0
        middle = length // 2 if is_even else length//2 + 1
        pos = 1
        cur = head

        while cur:
            if is_even:
                if pos <= middle:
                    stack.append(cur.val)
                else:
                    if cur.val != stack.pop():
                        return False
            else:
                if pos < middle:
                    stack.append(cur.val)
                elif pos > middle:
                    if cur.val != stack.pop():
                        return False
                else:
                    # Do nothing at the middle
                    pass

            cur = cur.next
            pos += 1

        return True

Javascript​

  • Time: O(NlogN)
  • Space: O(N)
var isPalindrome = function(head) {
    if (!head.next) return true;
    
    const array = [];
    let pointer = head;    
    while (pointer !== null) {
        array.push(pointer.val);
        pointer = pointer.next;        
    }
    
    let l = 0;
    let r = array.length - 1;
    while (l < r) {
        if (array[l] !== array[r]) return false;
        l++;
        r--;
    }
    return true;
};

Second Solution​

  • Time: O(2N)
  • Space: O(N/2)
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        length = 0
        
        cur = head
        while cur:
            length += 1
            cur = cur.next
        
        if not length:
            return False

        cur, stack = head, []
        for i in range(length>>1):
            stack.append(cur.val)
            cur = cur.next
        

        if length % 2 == 1:
            cur = cur.next

        while cur:
            if not stack or cur.val != stack[-1]:
                return False
            cur = cur.next
            stack.pop()
            
        return True