# Palindrome Linked List
**Difficulty:** EASY
[External](https://leetcode.com/problems/palindrome-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-linked-list
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List, Stack
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays), [Devsinc](https://scaleengineer.com/companies/devsinc), [Intuit](https://scaleengineer.com/companies/intuit), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Yandex](https://scaleengineer.com/companies/yandex), [ZScaler](https://scaleengineer.com/companies/zscaler), [Zoho](https://scaleengineer.com/companies/zoho), [IXL](https://scaleengineer.com/companies/ixl)
---
## Problem
Given the `head` of a singly linked list, return `true` _if it is a_ _palindrome_ _or_ `false` _otherwise_.

**Example 1:**

![](https://assets.glich.co/dsa/palindrome-linked-list/image0.jpg) 

**Input:** head = [1,2,2,1]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/palindrome-linked-list/image1.jpg) 

**Input:** head = [1,2]
**Output:** false

**Constraints:**

* The number of nodes in the list is in the range `[1, 105]`.
* `0 <= Node.val <= 9`

**Follow up:** Could you do it in `O(n)` time and `O(1)` space?

# Approaches
## Convert to Array Approach
Convert the linked list to an array and use two pointers to check if it's a palindrome.
**Time:** O(n) where n is the number of nodes in the linked list · **Space:** O(n) to store the array of values
**Pros:** Easy to implement and understand; Good for interviews when asked to provide a quick solution; Can handle null and single node cases easily
**Cons:** Uses extra space to store the array; Not the most efficient solution in terms of space complexity; Requires two passes through the data
### Explanation
This approach involves converting the linked list to an array first, then using two pointers (one from start and one from end) to check if the values match. While this is the most straightforward solution, it requires extra space to store the array.

```java
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        
        // Convert linked list to array
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }
        
        // Use two pointers to check palindrome
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}```
### Algorithm
1. Create an ArrayList to store the values
2. Traverse the linked list and add all values to the ArrayList
3. Use two pointers (left and right) starting from the beginning and end of the ArrayList
4. Compare values at left and right pointers
5. Move left pointer forward and right pointer backward
6. If any values don't match, return false
7. If all values match, return true

## Stack Approach
Use a stack to store the first half of the linked list and then compare with the second half.
**Time:** O(n) where n is the number of nodes in the linked list · **Space:** O(n/2) to store half of the elements in the stack
**Pros:** More space-efficient than converting to array; Only requires one pass through the linked list; Handles both odd and even length lists
**Cons:** Still requires extra space for the stack; More complex implementation than array approach; Not the most space-efficient solution possible
### Explanation
This approach uses a stack to store the first half of the linked list. First, find the middle of the linked list using slow and fast pointers. Push elements onto the stack until the middle is reached. Then compare the remaining elements with the top of the stack.

```java
class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode slow = head;
        ListNode fast = head;
        
        // Push first half elements onto stack
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // If odd length, skip middle element
        if (fast != null) {
            slow = slow.next;
        }
        
        // Compare second half with stack
        while (slow != null) {
            if (stack.isEmpty() || stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }
}```
### Algorithm
1. Initialize a stack and two pointers (slow and fast)
2. Move fast pointer twice as fast as slow pointer
3. Push elements onto stack until slow reaches middle
4. Skip middle element if list length is odd
5. Compare remaining elements with stack elements
6. Return false if any elements don't match
7. Return true if all elements match

## Reverse Second Half Approach
Find the middle of the linked list, reverse the second half, and compare with the first half.
**Time:** O(n) where n is the number of nodes in the linked list · **Space:** O(1) as it only uses a constant amount of extra space
**Pros:** Optimal space complexity O(1); Handles all cases efficiently; Meets the follow-up challenge requirement; Only requires one pass through the list
**Cons:** Modifies the original linked list structure; More complex implementation; Need to restore the original list if modification is not allowed
### Explanation
This is the most efficient approach that achieves O(1) space complexity. It works by first finding the middle of the linked list using slow and fast pointers, then reversing the second half of the list in-place, and finally comparing the first half with the reversed second half.

```java
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        // Find middle using slow/fast pointers
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Reverse the second half
        ListNode secondHalf = reverseList(slow.next);
        
        // Compare first half with reversed second half
        ListNode firstHalf = head;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        return true;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}```
### Algorithm
1. Find the middle of the linked list using slow and fast pointers
2. Reverse the second half of the linked list in-place
3. Compare the first half with the reversed second half
4. Return false if any values don't match
5. Return true if all values match

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public bool IsPalindrome ( ListNode head ) { ListNode slow = head ; ListNode fast = head . next ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } while ( pre != null ) { if ( pre . val != head . val ) { return false ; } pre = pre . next ; head = head . next ; } return true ; } }
```

### Java

```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; } * } */ class Solution { public boolean isPalindrome ( ListNode head ) { ListNode slow = head ; ListNode fast = head . next ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } while ( pre != null ) { if ( pre . val != head . val ) { return false ; } pre = pre . next ; head = head . next ; } return true ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {boolean} */ var isPalindrome =
  function (head) {
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
      slow = slow.next;
      fast = fast.next.next;
    }
    let cur = slow.next;
    slow.next = null;
    let pre = null;
    while (cur) {
      let t = cur.next;
      cur.next = pre;
      pre = cur;
      cur = t;
    }
    while (pre) {
      if (pre.val !== head.val) {
        return false;
      }
      pre = pre.next;
      head = head.next;
    }
    return true;
  };

```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: bool isPalindrome ( ListNode * head ) { ListNode * slow = head ; ListNode * fast = head -> next ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; } ListNode * pre = nullptr ; ListNode * cur = slow -> next ; while ( cur ) { ListNode * t = cur -> next ; cur -> next = pre ; pre = cur ; cur = t ; } while ( pre ) { if ( pre -> val != head -> val ) return false ; pre = pre -> next ; head = head -> next ; } return true ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def isPalindrome ( self , head : Optional [ ListNode ]) -> bool : slow , fast = head , head . next while fast and fast . next : slow , fast = slow . next , fast . next . next pre , cur = None , slow . next while cur : t = cur . next cur . next = pre pre , cur = cur , t while pre : if pre . val != head . val : return False pre , head = pre . next , head . next return True
```