# 234. Palindrome Linked List

### Description

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

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/palindrome-linked-list/)
* [ProgramCreek](https://www.programcreek.com/2014/07/leetcode-palindrome-linked-list-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** 1->2

**Output:** false
{% endtab %}

{% tab title="Example 2" %}
**Input:** 1->2->2->1

**Output:** true
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="ListNode" %}

```java
// Definition for singly-linked list.
public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) {
				this.val = val;
		}
		ListNode(int val, ListNode next) {
				this.val = val; this.next = next;
		}
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n)
 * Space complexity : O(n)
 */

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<>();

        // Convert LinkedList into ArrayList.
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // Use two-pointer technique to check for palindrome.
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            // Note that we must use ! .equals instead of !=
            // because we are comparing Integer, not int.
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n)
 * Space complexity : O(1)
 */

class Solution {
    private ListNode left;
    
    public boolean isPalindrome(ListNode head) {
        left = head;
        return isPalindromeHelper(head);
    }
    
    private boolean isPalindromeHelper(ListNode right) {
        if(right == null) {
            return true;
        }
        
        boolean tmp = isPalindromeHelper(right.next);
        
        if(!tmp) {
            return false;
        }
        
        boolean result = (left.val == right.val);
        left = left.next;
        
        return result;
    }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : O(n)
 * Space complexity : O(1)
 */
 
 class Solution {

    public boolean isPalindrome(ListNode head) {

        if (head == null) return true;

        // Find the end of first half and reverse second half.
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // Check whether or not there is a palindrome.
        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;
        }        

        // Restore the list and return the result.
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    // Taken from https://leetcode.com/problems/reverse-linked-list/solution/
    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;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Could you do it in O(n) time and O(1) space?


---

# 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://code-snippets.hbamithkumara.com/leetcode/problems/201-300/234.-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.