## Description

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

Given a singly linked list, determine if it is a palindrome.

**Example 1:**

Input:1->2Output:false

**Example 2:**

Input:1->2->2->1Output:true

**Follow up:**

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

## Explanation

A palindrome, and its reverse, are identical to each other.

## Python Solution

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
reversed_head = self.reverse(head)
while (head != None and reversed_head != None):
if (head.val != reversed_head.val):
return False
head = head.next
reversed_head = reversed_head.next
return True
def reverse(self, head):
prev = None
dummy = ListNode(0)
dummy.next = head
current = head
while (current != None):
new = ListNode(current.val)
new.next = prev
prev = new
current = current.next
head = dummy.next
return prev
```

- Time complexity: O(N).
- Space complexity: O(1).

## One Thought to “LeetCode 234. Palindrome Linked List”