> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/bu-chong-81100-dao/234.-palindrome-linked-list.md).

# 234. Palindrome Linked List

\# Easy

{% hint style="info" %}
Method 1:

Two pointers, one list to store the first half elements in order.

`1 -> 2 -> 1` and `1 -> 2 -> 2 -> 1` are palindrome linked list.

Two cases: the length of the linked list is **odd** or **even**.

Method 2:

**slow**, **fast** pointers. When slow goes to the middle of the list, reverse the last half of list, then compare front to end one by one.
{% endhint %}

{% tabs %}
{% tab title="Python-method1" %}

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # edge case
        if head == None or head.next == None:
            return True
        
        collect = []
        tmp = head
        while True:
            collect.append(head.val)
            # 判断nodelist的长度是奇数还是偶数
            if tmp.next == None:   # 奇数
                flag = 1
                break
            elif tmp.next.next == None:   # 偶数
                flag = -1
                break
            tmp = tmp.next.next
            head = head.next
        
        if flag == 1:   # the nodelist is odd
            while head != None:
                if collect.pop() != head.val:
                    return False
                head = head.next
        else:    # the nodelist is even
            while head.next != None:
                head = head.next
                if collect.pop() != head.val:
                    return False
        
        return True
        
```

> Time = $$O(n)$$ , Space = $$O(n)$$, How to reduce space to $$O(1)$$ ?
> {% endtab %}

{% tab title="Python-method2" %}

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # edge case
        if head == None or head.next == None:
            return True
        
        # find the middle position of the nodelist
        slow = head
        fast = head
        while fast.next != None and fast.next.next != None:
            fast = fast.next.next
            slow = slow.next

        # reverse the last half of the nodelist
        last = slow.next
        while last.next != None:
            tmp = last.next
            last.next = tmp.next
            tmp.next = slow.next
            slow.next = tmp
        
        # compare the front with the end one by one
        while slow.next != None:
            slow = slow.next
            if head.val != slow.val:
                return False
            head = head.next
            
        return True
```

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MK3Q2ZmjtmXYFqPBLyx%2F-MK3TsL8c5u2mPVUreNH%2F1603171732237.jpg?alt=media\&token=83cc592c-a021-4e6b-a35c-b0ad87092dc5)

> Time = $$O(n)$$ , Space = $$O(1)$$ 
> {% endtab %}
> {% endtabs %}