Palindrome Linked List solution and explanation
TCS
Google
Infosys
9 more videos on this problem
Palindrome Linked List - Leetcode 234 - PythonNeetCode · 11:06 · 128K views
LeetCode Palindrome Linked List Solution Explained - JavaNick White · 9:35 · 117K views
Palindrome Linked List (LeetCode 234) | Full solution with trick | Study AlgorithmsNikhil Lohia · 14:48 · 26K views
LeetCode 234. Palindrome Linked List [Solution + Code Explained ]jayati tiwari · 14:00 · 9K views
Palindrome Linked List - LeetCode 234 - Coding Interview QuestionsOne Code Man · 9:27 · 8K views
LEETCODE 234 (JAVASCRIPT) | PALINDROME LINKED LISTAndy Gala · 10:19 · 4K views
[Java] Leetcode 234. Palindrome Linked List [Fast & Slow Pointers #4]Eric Programming · 9:31 · 3K views
Leetcode | 234. Palindrome Linked List | Easy | Java SolutionDeveloper Docs · 5:51 · 3K views
Palindrome Linked List - LeetCode 234 - JavaScriptAlgoJS · 5:48 · 1K views
#234 - Palindrome Linked List - LeetCode - Python - TamilCode Meal · 20:25 · 1K views
The problem
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1] Output: true
Example 2:
Input: head = [1,2] Output: false
Constraints:
- The number of nodes in the list is in the range
[1, 105]. 0 <= Node.val <= 9
O(n) time and O(1) space?Approach overview
Problem Overview: You are given the head of a singly linked list. The goal is to determine whether the sequence of node values reads the same forward and backward. In other words, check if the linked list forms a palindrome without modifying the logical order of elements.
Approach 1: Convert to Array and Use Two Pointers (O(n) time, O(n) space)
This approach copies the linked list values into a dynamic array or vector while iterating through the list once. After that, apply the classic two pointers technique: one pointer starts at the beginning of the array and the other at the end. Compare elements while moving inward. If every pair matches, the sequence is a palindrome.
The key insight is that arrays allow constant-time index access, which makes comparing mirrored elements trivial. This solution is straightforward to implement and easy to reason about, especially for beginners. The tradeoff is additional memory because the entire list is stored in an array.
Approach 2: Reverse Second Half and Compare (O(n) time, O(1) space)
This is the optimal in-place technique commonly expected in interviews. First locate the midpoint of the list using the fast and slow pointer technique from two pointers. When the fast pointer reaches the end, the slow pointer sits at the middle. Reverse the second half of the list starting from that midpoint.
Once reversed, compare nodes from the beginning of the list with nodes from the reversed half. If every value matches, the linked list is a palindrome. Reversal works because the second half now appears in reverse order, allowing direct pairwise comparison.
The advantage is constant extra memory since operations happen directly on the linked list. The only additional work is reversing half the list and optionally restoring it afterward. The algorithm performs a single pass to find the midpoint, another pass to reverse, and a final comparison pass, which still results in linear time.
Recommended for interviews: Start by explaining the array approach to demonstrate the core palindrome idea. Then optimize to the in-place method by reversing the second half. Interviewers typically expect the O(n) time and O(1) space solution because it shows comfort with linked list manipulation and pointer techniques.
Approach 1: Reverse Second Half and Compare
This approach involves reversing the second half of the linked list and then comparing it with the first half. If they are identical, the linked list is a palindrome. The steps include:
- Use two pointers (slow and fast) to find the middle of the linked list.
- Reverse the second half of the linked list.
- Compare the first half and the reversed second half of the list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head):
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev
def isPalindrome(self, head):
if not head or not head.next:
return True
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second_half = self.reverseList(slow)
first_half = head
while second_half:
if first_half.val != second_half.val:
return False
first_half = first_half.next
second_half = second_half.next
return Trueclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode nextNode = head.next;
head.next = prev;
prev = head;
head = nextNode;
}
return prev;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = reverseList(slow);
ListNode firstHalf = head;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* current = head;
while (current != NULL) {
ListNode* nextNode = current->next;
current->next = prev;
prev = current;
current = nextNode;
}
return prev;
}
bool isPalindrome(ListNode* head) {
if (head == NULL || head->next == NULL) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second_half = reverseList(slow);
ListNode* first_half = head;
while (second_half != NULL) {
if (first_half->val != second_half->val) return false;
first_half = first_half->next;
second_half = second_half->next;
}
return true;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
let nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}
function isPalindrome(head) {
if (!head || !head.next) return true;
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
let secondHalf = reverseList(slow);
let firstHalf = head;
while (secondHalf !== null) {
if (firstHalf.val !== secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}#include <stdbool.h>
#include <stdio.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* current = head;
struct ListNode* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
bool isPalindrome(struct ListNode* head) {
if (head == NULL || head->next == NULL) return true;
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* reversedSecondHalf = reverseList(slow);
struct ListNode* p1 = head;
struct ListNode* p2 = reversedSecondHalf;
while (p2 != NULL) {
if (p1->val != p2->val) return false;
p1 = p1->next;
p2 = p2->next;
}
return true;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next;
current.next = prev;
prev = current;
current = nextNode;
}
return prev;
}
public bool IsPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = ReverseList(slow);
ListNode firstHalf = head;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) return false;
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
}The Python solution follows the same approach of reversing the second half of the list and then comparing it with the first half to check for palindrome characteristics.
Time Complexity: O(n) due to the iterations for finding the middle and reversing the list.
Space Complexity: O(1) for in-place reversals.
Approach 2: Convert to Array and Use Two Pointers
In this approach, convert the linked list into an array and utilize a two-pointer technique to determine if it forms a palindrome. The steps are as follows:
- Traverse the linked list and store its elements in an array.
- Use two pointers, one starting at the beginning and the other at the end of the array, to compare values.
- If all corresponding elements are identical, the list is a palindrome.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
values = []
current = head
while current:
values.append(current.val)
current = current.next
left, right = 0, len(values) - 1
while left < right:
if values[left] != values[right]:
return False
left, right = left + 1, right - 1
return Trueimport java.util.ArrayList;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public boolean isPalindrome(ListNode head) {
ArrayList<Integer> values = new ArrayList<>();
ListNode current = head;
while (current != null) {
values.add(current.val);
current = current.next;
}
int left = 0, right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) return false;
left++;
right--;
}
return true;
}
}#include <vector>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool isPalindrome(ListNode* head) {
vector<int> values;
ListNode* current = head;
while (current != nullptr) {
values.push_back(current->val);
current = current->next;
}
int left = 0, right = values.size() - 1;
while (left < right) {
if (values[left] != values[right]) return false;
left++;
right--;
}
return true;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function isPalindrome(head) {
const values = [];
let current = head;
while (current !== null) {
values.push(current.val);
current = current.next;
}
let left = 0, right = values.length - 1;
while (left < right) {
if (values[left] !== values[right]) return false;
left++;
right--;
}
return true;
}#include <stdbool.h>
#include <stdio.h>
struct ListNode {
int val;
struct ListNode *next;
};
bool isPalindrome(struct ListNode* head) {
int values[100000];
int size = 0;
struct ListNode* current = head;
while (current != NULL) {
values[size++] = current->val;
current = current->next;
}
int left = 0, right = size - 1;
while (left < right) {
if (values[left++] != values[right--]) return false;
}
return true;
}using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public bool IsPalindrome(ListNode head) {
List<int> values = new List<int>();
ListNode current = head;
while (current != null) {
values.Add(current.val);
current = current.next;
}
int left = 0, right = values.Count - 1;
while (left < right) {
if (values[left] != values[right]) return false;
left++;
right--;
}
return true;
}
}The Python solution utilizes a list to grab all node values in sequence. The double-pointer checking method then efficiently checks for palindrome properties.
Time Complexity: O(n), where n is list size traversed once.
Space Complexity: O(n) due to external list used to store values.
Approach 3: Fast and Slow Pointers
We can use fast and slow pointers to find the middle of the linked list, then reverse the right half of the list. After that, we traverse both halves simultaneously, checking if the corresponding node values are equal. If any pair of values is unequal, it's not a palindrome linked list; otherwise, it is a palindrome linked list.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function isPalindrome(head: ListNode | null): boolean {
let slow: ListNode = head,
fast: ListNode = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
let cur: ListNode = slow.next;
slow.next = null;
let prev: ListNode = null;
while (cur != null) {
let t: ListNode = cur.next;
cur.next = prev;
prev = cur;
cur = t;
}
while (prev != null) {
if (prev.val != head.val) return false;
prev = prev.next;
head = head.next;
}
return true;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
var pre *ListNode
cur := slow.Next
for cur != nil {
t := cur.Next
cur.Next = pre
pre = cur
cur = t
}
for pre != nil {
if pre.Val != head.Val {
return false
}
pre, head = pre.Next, head.Next
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Second Half and Compare | Time Complexity: O(n) due to the iterations for finding the middle and reversing the list. |
| Convert to Array and Use Two Pointers | Time Complexity: O(n), where n is list size traversed once. |
| Fast and Slow Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Array and Two Pointers | O(n) | O(n) | When simplicity matters and extra memory is acceptable |
| Reverse Second Half and Compare | O(n) | O(1) | Best for interviews and memory-constrained scenarios |
Frequently asked questions
Is Palindrome Linked List easy or hard?
Palindrome Linked List is classified as an Easy problem on LeetCode. The array-based solution is straightforward, while the in-place reversal technique introduces intermediate-level linked list manipulation concepts.
Palindrome Linked List Python/Java solution
In Python or Java, the typical solution either copies node values into a list and applies a two-pointer check or reverses the second half of the linked list before comparing nodes. Both implementations run in O(n) time, with the optimal version using O(1) extra space.
How to solve Palindrome Linked List in O(n)?
Traverse the list with slow and fast pointers to locate the midpoint. Reverse the second half of the linked list in place, then compare nodes from the start and the reversed half one by one. If all values match, the list is a palindrome. The entire process takes linear time.
What is the best approach for Palindrome Linked List?
The most efficient approach reverses the second half of the linked list and compares it with the first half. This method runs in O(n) time and uses O(1) extra space. Interviewers prefer this approach because it demonstrates pointer manipulation and linked list reversal skills.
Is Palindrome Linked List asked at Google/Amazon/Meta?
Palindrome Linked List is a common interview question at companies like Amazon, Microsoft, and Meta because it tests linked list traversal, pointer manipulation, and in-place optimization. Variations also appear in technical screening rounds.
What data structure is used in Palindrome Linked List?
The problem primarily uses a singly linked list. Some solutions temporarily use an auxiliary array or stack to store node values, while the optimal approach relies on pointer techniques and in-place linked list reversal.
What is the time complexity of Palindrome Linked List?
The optimal solution runs in O(n) time because the list is traversed a constant number of times: once to find the middle, once to reverse the second half, and once to compare values. Simpler solutions using an array also run in O(n) time but require O(n) additional space.