# 234. Palindrome Linked List

### On This Page

## Problem Statement

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

## Naive Solution

A simple solution to this problem is to:

- traverse the linked list
- storing the value of each node in an array.

Then, we could compare the array with its reversed version.

If they match, the linked list is a palindrome. Otherwise, it is not.

This solution takes `O(n)`

time (where `n`

is the number of nodes in the list), as we need to traverse the list once.

However, it also takes `O(n)`

space, as we store the value of each node in an array.

## Approach

To solve the problem in `O(n)`

time and `O(1)`

space, we can use the two-pointer technique to **find the middle of the linked list**. Then, we can reverse the second half of the list in-place. After that, we can compare the first half with the reversed second half. If they match, the list is a palindrome.

Reversing a linked list in-place involves changing the next pointers of the nodes to point to the previous node. This process can be done with a constant amount of space.

## Steps

- Initialize two pointers: slow and fast at the head of the list.
- Move slow one step at a time and fast two steps at a time.
- When fast reaches the end of the list, slow will be at the middle.

- Reverse the second half of the list starting from slow.
- Compare the first half of the list with the reversed second half.
- If they match, return true.
- If they don’t, return false.

## Solution

```
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
slow = fast = head
# find the mid node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# reverse the second half
prev = None
cur = slow
while cur: # 1 [1 2 3 4]
nxt = cur.next # 2
cur.next = prev # 1.next = None
prev = cur # 1, at the end of loop will be 4
cur = nxt # 2
# compare the first and second half nodes
while prev:
if prev.val != head.val:
return False
prev = prev.next
head = head.next
return True
```

### Debug of Reversing

Assuming we have a linked list as `[1,2,3,4,5,6]`

and slow initially points to `4`

. Result should be `[6,5,4,3,2,1]`

Initial state:

- Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
- cur points to 4
- prev = None

- First iteration:

- nxt is assigned 5 (the next node after cur)
- cur.next (the next node after 4) is assigned None
- prev is assigned 4
- cur is assigned 5 (nxt)

After first iteration:

- Linked list: 1 -> 2 -> 3 -> 4 -> None, 5 -> 6
- cur points to 5
- prev points to 4

- Second iteration:

- nxt is assigned 6
- cur.next (the next node after 5) is assigned 4 (prev)
- prev is assigned 5
- cur is assigned 6 (nxt)

After second iteration:

- Linked list: 1 -> 2 -> 3 -> 4 -> None, 5 -> 4, 6
- cur points to 6
- prev points to 5

- Third iteration:

- nxt is assigned None
- cur.next (the next node after 6) is assigned 5 (prev)
- prev is assigned 6
- cur is assigned None (nxt)

After third iteration:

- Linked list: 1 -> 2 -> 3 -> 4 -> None, 5 -> 4, 6 -> 5
- cur points to None
- prev points to 6

- Since
`cur`

is`None`

, we exit the while loop.

Now `prev`

is pointing to the `head`

of the reversed second half of the list.

The list now looks like this: `1 -> 2 -> 3 -> 4 -> None and 6 -> 5 -> 4 -> None`

.