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?

The description was taken from https://leetcode.com/problems/palindrome-linked-list/.

`#O(N) Time, O(1) Space`

**class** **Solution**:

**def** **isPalindrome**(self, head):

fast = slow = head

**while** fast **and** fast.next:

fast = fast.next.next

slow = slow.next

previous, current = None, slow

**while** current:

bridge = current.next

current.next = previous

previous = current

current = bridge

current = previous

**while** current **is** **not** None:

**if** current.val != head.val:

**return** False

current = current.next

head = head.next

**return** True

This problem can be solved with the combined solutions from *Middle of the Linked List* and *Reverse Linked List*.

We can use a slow and fast pointer to get the middle element and from there, we will reverse the node pointers from the middle element to the end of the list.

That will allow us to break the linked list at the middle and have two pointers to make the old tail be the new head of a separate sublist. We can compare the values of the nodes at these two pointers and if they match, we will move them inward to compare the next two. If there is no mismatch in values, the linked list is a palindrome.

Let's start off by initializing our fast and slow pointers at the head of the linked list.

` fast = slow = head`

Then, we will traverse the list with our pointers. During each iteration, we will increment the slow pointer once and the fast pointer twice.

Once the fast pointer is at the end of the list, the slow pointer will be halfway to the end.

` `**while** fast **and** fast.next:

` fast = fast.next.next`

` slow = slow.next`

Once the slow pointer is at the midpoint, we will begin reversing the second half of the list.

We will do this by utilizing three pointers. Our

pointer**previous **** **will be used to track the previous node,

will be used to track the current node, and **current**

will be used to track the next node.**bridge**

We will initialize our previous and current pointers, with the current pointer being where

was. The node the slow pointer is at will be the head of its sublist once reversed.**slow**

` previous, current = None, slow`

While the current pointer isn't at a null node, we continue moving down the list, setting each current pointer's next reference to the previous node.

` `

**while** current:

At the beginning of each iteration, we will save

as the next node.**bridge **

` bridge = current.next`

We want to do this because once we overwrite **current.next**

and set it to the previous node, we will lose our bridge to get to the next node. ** **

Once we saved our bridge, we will overwrite the reference to our next node by setting it to the previous node,

. **previous**

` current.next = previous`

We will then move our previous pointer to the current pointer, and our current pointer will cross the bridge to the next node.

` previous = current`

current = bridge

Once we have broke from the loop, that means that the current is now at the null node, so we'll set it back a node to its previous value.

` current = previous`

Once we have reversed the node pointers, our list will basically go from this:

1->2->3->3->2->1**head**`None`

to this:

1->2->3->**head**`None`

<-3<-2<-1**current**

While

has not reached the **current **

value, we will keep moving it and the head pointer to their next places.**None **

If there is a mismatch in values, we will return false.

` `**while** current **is** **not** None:

**if** current.val != head.val:

**return** False

current = current.next

head = head.next

Otherwise, if we break from the loop then all of the values match up and we will return true.

` `

**return** True