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

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