Palindrome Linked List

Definition for Singly-Linked List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Solution

All solutions below take linear time.

Linear Space

Two Pointers

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    stk = []
    p = head
    while p is not None:
        stk.append(p)
        p = p.next
    
    p = head
    while len(stk) > 0 and stk.pop().val == p.val:
        p = p.next

    return len(stk) == 0

Recursion

def isPalindrome(self, head: ListNode) -> bool:
    self.front = head

    def check(curr=head):
        if curr:
            if not check(curr.next):
                return False
            if curr.val != self.front.val:
                return False
            self.front = self.front.next
        return True

    return check()

Follow Up

Could you do it in $O(n)$ time and $O(1)$ space?

Constant Space

Fast and Slow Pointers

• use 2 pointers (fast & slow), find middle pointer
• reverse latter part of linked list
• compare 2 pointers to check if palindrome

def isPalindrome(self, head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    p2 = self.reverseLinkedList(slow)
    p1 = head
    while p2 is not None:
        if p1.val != p2.val:
            return False
        p1 = p1.next
        p2 = p2.next
    return True

def reverseLinkedList(self, head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev