Palindrome Linked List


# Definition for Singly-Linked List

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

# Solution

All solutions below take linear time.

# Linear Space

# Two Pointers

def isPalindrome(self, head: ListNode) -> bool:
    vals = []
    curr = head
    while curr:
        curr =

    return vals == vals[::-1]

# Recursion

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

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

    return check()

# Follow Up

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

# Constant Space

# Fast and Slow Pointers

Need to reverse then 2nd half to save space. As good practice, should reverse it back before return.

def isPalindrome(self, head: ListNode) -> bool:
    if not head:
        return True

    # find tail node of the 1st half
    fst_half_end = self.end_of_fst_half(head)
    # reverse the 2nd half
    snd_half_start = self.reverse_list(

    # check if palindrome
    res = True
    fst, snd = head, snd_half_start
    while res and snd:
        if fst.val != snd.val:
            res = False
        fst, snd =,

    # restore linked list = self.reverse_list(snd_half_start)
    return res

def end_of_fst_half(self, head):
    fast = head
    slow = head
    while and
        fast =
        slow =
    return slow

def reverse_list(self, head):
    prev = None
    curr = head
    while curr:
        temp = = prev
        prev = curr
        curr = temp
    return prev