# 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:**

Input: head = [1,2,2,1]
Output: true

**Example 2:**

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

**Constraints:**

- The number of nodes in the list is in the range <code>[1, 10⁵]</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

# 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

/**
 * 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)

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

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

p.s.
1.

ListNode *h2 = reverseList(slow);

為何是reverse slow而不是reverse head?
因為head的最後一個還需要判斷是等於nullptr還是slow, reverse slow的話就少了這一個判斷

2.

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

為何是 while(h1) 而不是 while(h1 && h2)?
因為h1的長度小於等於h2