> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/201-300/234.-palindrome-linked-list.md).

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