---
# System prepended metadata

title: LC 234. Palindrome Linked List
tags: [easy, leedcode, Linked List, python, c++]

---

# LC 234. Palindrome Linked List

### [Problem link](https://leetcode.com/problems/palindrome-linked-list/)

###### tags: `leedcode` `python` `c++` `easy` `Linked List`

Given the <code>head</code> of a singly linked list, return <code>true</code> if it is a **palindrome-sequence** or <code>false</code> otherwise.

**Example 1:** 
![](https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg)
```
Input: head = [1,2,2,1]
Output: true
```

**Example 2:** 
![](https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg)

```
Input: head = [1,2]
Output: false
```

 **Constraints:** 

- The number of nodes in the list is in the range <code>[1, 10<sup>5</sup>]</code>.
- <code>0 <= Node.val <= 9</code>


 **Follow up:**  Could you do it in <code>O(n)</code> time and <code>O(1)</code> space?
## Solution 1 - Linked List(Follow up)
#### Python
```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: Optional[ListNode]) -> bool:
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        node = None
        while slow:
            tmp = slow.next
            slow.next = node
            node = slow
            slow = tmp

        cur = head
        while node:
            if cur.val != node.val:
                return False
            cur = cur.next
            node = node.next

        return True
```
```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head;
        ListNode *prev = nullptr;
        ListNode *next = nullptr;
        while (cur) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    bool isPalindrome(ListNode* head) {
        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *prev = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        if (prev) {
            prev->next = nullptr;
        }
        ListNode *h1 = head;
        ListNode *h2 = reverseList(slow);

        while (h1) {
            if (h1->val != h2->val) {
                return false;
            }
            h1 = h1->next;
            h2 = h2->next;
        }
        return true;
    }
};
```

>### Complexity
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(1)             |


## Note
[代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0234.%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8.md)
[原地反轉鏈表（In-place Reversal of Linked-List）](https://hackmd.io/@Hsins/in-place-reversal-of-linked-List)

建議看完後自己拿筆模擬一次.

```python=
1 -> 2 -> 2 -> 1 -> null  
          ^          ^
         slow       fast
然後反轉slow開始的linked list
反轉後:
head: 1  ->  2  ->  2  ->  null
node: 1  ->  2  -> null
```

p.s.
1.
```cpp=
ListNode *h2 = reverseList(slow);
```
為何是reverse slow而不是reverse head?
因為head的最後一個還需要判斷是等於nullptr還是slow, reverse slow的話就少了這一個判斷

2.
```cpp=
while (h1) {
    if (h1->val != h2->val) {
        return false;
    }
    h1 = h1->next;
    h2 = h2->next;
}
```
為何是 while(h1) 而不是 while(h1 && h2)?
因為h1的長度小於等於h2

