# Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

**Example 1:**

```
Input: 1->2
Output: false
```

**Example 2:**

```
Input: 1->2->2->1
Output: true
```

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

## Analysis

由于单链表没有反向指针，因此就需要将链表分为左右两部分进行比较。找中点可以用快满指针，找到之后翻转右边一半的链表，这时就可以进行一对一比较了。

参考： <https://leetcode.com/problems/palindrome-linked-list/discuss/64501/Java-easy-to-understand>

In the beginning, set two pointers`fast`and`slow`starting at the head.

```
1 -> 1 -> 2 -> 1 -> null 
sf
```

(1) **Move:**`fast`pointer goes to the end, and`slow`goes to the middle.

```
1 -> 1 -> 2 -> 1 -> null 
          s          f
```

(2) **Reverse:** the right half is reversed, and`slow`pointer becomes the 2nd head.

```
1 -> 1    null <- 2 <- 1           
h                      s
```

(3) **Compare:** run the two pointers`head`and`slow`together and compare.

```
1 -> 1    null <- 2 <- 1             
     h            s
```

## Solution

Find Mid Point + Reverse + Compare --- O(n) time, O(1) space

```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) {
        ListNode fast, slow;
        fast = head;
        slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;

        while (fast != null && slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode tmpNext = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmpNext;
        }
        return prev;
    }
}
```

Don't need to make the right half smaller: <https://leetcode.com/problems/palindrome-linked-list/discuss/64501/Java-easy-to-understand/66206>

```java
public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow);
        while (head != null && slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
```

## Reference

<https://leetcode.com/problems/palindrome-linked-list/discuss/64501/Java-easy-to-understand>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/linked_list/palindrome-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.