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

# 0234. Palindrome Linked List

<https://leetcode.com/problems/palindrome-linked-list>

## Description

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

**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 `[1, 105]`.
* `0 <= Node.val <= 9`

**Follow up:** Could you do it in `O(n)` time and `O(1)` space?

## ac

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // edge cases
        if (head == null || head.next == null) return true;

        // 2 pointers
        ListNode slow = head.next, fast = head.next.next, r = head, prev = null;
        int cnt = 2;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            cnt += 2;
            // reverse 
            r.next = prev;
            prev = r;
            r = slow;
            slow = slow.next;
        }
        r.next = prev;
        if (fast != null) cnt++;

        // check
        ListNode left = r, right = cnt % 2 == 0 ? slow : slow.next;
        while (left != null && right != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }
}
```

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // edge cases
        if (head == null || head.next == null) return true;

        // 2 pointers, fast/slow, reverse first half
        ListNode fast = head, slow = head, prev = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;

            ListNode tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }

        // left and right side
        ListNode left = prev;
        ListNode right = fast == null ? slow : slow.next;

        // validate
        while (left != null && right != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }
}
```