Problem Statement:
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Examples:
- Input: head = [1,2,2,1]
Output: true - Input: head = [1,2]
Output: false
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
Approach 1:
- Traverse the linked list and store values in an array.
- Check whether the array is a palindrome by comparing elements from start and end moving towards the center.
Time and Space Complexity:
- Time Complexity: O(n), where n is the number of nodes.
- Space Complexity: O(n), for the array storage.
var isPalindrome = function(head) {
let arr = [];
let curr = head;
while (curr !== null) {
arr.push(curr.val);
curr = curr.next;
}
let left = 0, right = arr.length - 1;
while (left < right) {
if (arr[left++] !== arr[right--]) return false;
}
return true;
};
class Solution(object):
def isPalindrome(self, head):
vals = []
while head:
vals.append(head.val)
head = head.next
return vals == vals[::-1]
class Solution {
public boolean isPalindrome(ListNode head) {
List vals = new ArrayList<>();
while (head != null) {
vals.add(head.val);
head = head.next;
}
int left = 0, right = vals.size() - 1;
while (left < right) {
if (!vals.get(left++).equals(vals.get(right--))) return false;
}
return true;
}
}
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
while (head) {
vals.push_back(head->val);
head = head->next;
}
int left = 0, right = vals.size() - 1;
while (left < right) {
if (vals[left++] != vals[right--]) return false;
}
return true;
}
};
bool isPalindrome(struct ListNode* head) {
int vals[100000], i = 0, left, right;
while (head) {
vals[i++] = head->val;
head = head->next;
}
left = 0; right = i - 1;
while (left < right) {
if (vals[left++] != vals[right--]) return false;
}
return true;
}
public class Solution {
public bool IsPalindrome(ListNode head) {
List<int> vals = new List<int>();
while (head != null) {
vals.Add(head.val);
head = head.next;
}
int left = 0, right = vals.Count - 1;
while (left < right) {
if (vals[left++] != vals[right--]) return false;
}
return true;
}
}
Approach 2:
- Use two pointers (
slowandfast) to find the middle of the linked list. - Reverse the second half of the list.
- Compare the first and second halves node by node.
Time and Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(1)
var isPalindrome = function(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
let prev = null;
while (slow) {
let temp = slow.next;
slow.next = prev;
prev = slow;
slow = temp;
}
// Compare two halves
let first = head, second = prev;
while (second) {
if (first.val !== second.val) return false;
first = first.next;
second = second.next;
}
return true;
};
class Solution:
def isPalindrome(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
while slow:
temp = slow.next
slow.next = prev
prev = slow
slow = temp
# Compare halves
first, second = head, prev
while second:
if first.val != second.val:
return False
first = first.next
second = second.next
return True
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
ListNode prev = null;
while (slow != null) {
ListNode temp = slow.next;
slow.next = prev;
prev = slow;
slow = temp;
}
// Compare halves
ListNode first = head, second = prev;
while (second != null) {
if (first.val != second.val) return false;
first = first.next;
second = second.next;
}
return true;
}
}
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// Reverse second half
ListNode* prev = nullptr;
while (slow) {
ListNode* temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
// Compare halves
ListNode* first = head;
while (prev) {
if (first->val != prev->val) return false;
first = first->next;
prev = prev->next;
}
return true;
}
};
bool isPalindrome(struct ListNode* head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// Reverse second half
struct ListNode* prev = NULL;
while (slow) {
struct ListNode* temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
// Compare halves
struct ListNode* first = head;
while (prev) {
if (first->val != prev->val) return false;
first = first->next;
prev = prev->next;
}
return true;
}
public class Solution {
public bool IsPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
ListNode prev = null;
while (slow != null) {
ListNode temp = slow.next;
slow.next = prev;
prev = slow;
slow = temp;
}
// Compare halves
ListNode first = head, second = prev;
while (second != null) {
if (first.val != second.val) return false;
first = first.next;
second = second.next;
}
return true;
}
}
