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

# Palindrome Linked List

## Question ([LC.234](https://leetcode.com/problems/palindrome-linked-list/description/))

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

## Example

```
I: 1 -> 2 -> 1
O: true
```

## Analysis

Need to use L/R pointers to compare the first half and the second half.

## Approach

```
Step 1 Find the mid point
Step 2 reverse the second half
Step 3 compare two lists
Step 4 (optional) reverse the second half back
```

## Code

```java
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    ListNode mid = findMid(head);
    ListNode l2 = reverseList(mid);
    ListNode l1 = head;
    // compare
    while (l2 != mid) {
        if (l1.val == l2.val) {
            l1 = l1.next;
            l2 = l2.next;
        } else {
            break;
        }
    }
    return l2.val == l1.val;
}

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

private ListNode reverseList(ListNode head) {
    ListNode prev = head;
    ListNode current = head.next;
    ListNode temp;
    while (current != null) {
        temp = current.next;
        current.next = prev;
        prev = current;
        current = temp;
    }
    return prev;
}
```