> For the complete documentation index, see [llms.txt](https://wentao-shao.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://wentao-shao.gitbook.io/leetcode/linked-list/234.palindrome-linked-list.md).

# 234.Palindrome-Linked-List

## 234. Palindrome Linked List

## 题目地址

<https://leetcode.com/problems/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?
```

## 代码

### Approach #1 Copy into ArrayList and then Use Two Pointer Technique

**Complexity Analysis**

* Time complexity : O(n)
* Space complexity : O(n)

```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) {
        List<Integer> vals = new ArrayList<>();
    ListNode currentNode = head;
    while (currentNode != null) {
      vals.add(currentNode.val);
      currentNode = currentNode.next;
    }

    int front = 0;
    int back = vals.size() - 1;
    while (front < back) {
      if (!vals.get(front).equals(vals.get(back))) {
        return false;
      }
      front++;
      back--;
    }

    return true;
  }
}
```

### Approach #2 Recursive - DFS

```java
class Solution {
  private ListNode frontPointer;

  public boolean isPalindrome(ListNode head) {
    frontPointer = head;
    return recursivelyCheck(head);
  }

  private boolean recursivelyCheck(ListNode currentNode) {
    if (currentNode != null) {
      if (!recursivelyCheck(currentNode.next))    return false;
      if (currentNode.val != frontPointer.val)    return false;

      frontPointer = frontPointer.next;
    }
    return true;
  }

}
```

### Approach #3 Reverse Second Half In-place

```java
class Solution {
  public boolean isPalindrome(ListNode head) {
    if (head == null)    return true;

    ListNode firstHalfEnd = endOfFirstHalf(head);
    ListNode secondHalfStart = reverseList(firstHalfEnd.next);

    ListNode p1 = head;
    ListNode p2 = secondHalfStart;
    boolean result = true;
    while (result && p2 != null) {
      if (p1.val != p2.val)        result = false;
      p1 = p1.next;
      p2 = p2.next;
    }

    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
  }

  private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
      ListNode nextTemp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = nextTemp;
    }
    return prev;
  }

  private ListNode endOfFirstHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }
    return slow;
  }
}
```