class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# Find the end of first half and reverse second half
def end_of_first_half(node):
fast = slow = node
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow
def reverse(node):
prev = None
while node:
next_node = node.next
node.next = prev
prev = node
node = next_node
return prev
if not head or not head.next:
return True
first_half_end = end_of_first_half(head)
second_half_start = reverse(first_half_end.next)
# Compare both halves
p1, p2 = head, second_half_start
result = True
while p2:
if p1.val != p2.val:
result = False
break
p1 = p1.next
p2 = p2.next
# Restore the list (optional)
first_half_end.next = reverse(second_half_start)
return result
/**
* 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) {
if (!head || !head->next) return true;
// Find the end of the first half
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// Reverse the second half
ListNode* prev = nullptr;
ListNode* curr = slow->next;
while (curr) {
ListNode* next_temp = curr->next;
curr->next = prev;
prev = curr;
curr = next_temp;
}
// Check palindrome
ListNode* p1 = head;
ListNode* p2 = prev;
bool result = true;
while (p2) {
if (p1->val != p2->val) {
result = false;
break;
}
p1 = p1->next;
p2 = p2->next;
}
// Optional: Restore the list
curr = prev;
prev = nullptr;
while (curr) {
ListNode* next_temp = curr->next;
curr->next = prev;
prev = curr;
curr = next_temp;
}
slow->next = prev;
return result;
}
};
/**
* 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) {
if (head == null || head.next == null) return true;
// Find the end of first half
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
ListNode prev = null, curr = slow.next;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// Compare halves
ListNode p1 = head, p2 = prev;
boolean result = true;
while (p2 != null) {
if (p1.val != p2.val) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// Optional: Restore the list
curr = prev;
prev = null;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
slow.next = prev;
return result;
}
}
/**
* 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) {
if (!head || !head.next) return true;
// Find end of first half
let slow = head, fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
let prev = null, curr = slow.next;
while (curr) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// Compare halves
let p1 = head, p2 = prev;
let result = true;
while (p2) {
if (p1.val !== p2.val) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
// Optional: Restore list
curr = prev;
prev = null;
while (curr) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
slow.next = prev;
return result;
};
You are given the head of a singly linked list. Your task is to determine whether the values of the nodes in the linked list form a palindrome. A palindrome is a sequence that reads the same backward as forward.
Constraints:
At first glance, it might seem easiest to convert the linked list into an array, then check if the array is a palindrome. This would require O(n) extra space, which may not be allowed for large lists or if an in-place solution is desired.
Next, we consider whether we can compare nodes directly in the linked list. Since it's singly linked, we cannot traverse backward easily. This leads us to think about strategies that allow us to compare the first and last halves of the list without extra space.
The key insight is to reverse the second half of the list, so we can compare the first half and the reversed second half node by node. After the comparison, we can restore the original list structure if needed.
slow and fast. Move slow one step at a time and fast two steps at a time.fast reaches the end, slow will be at the midpoint.slow.next, reverse the second half of the list in-place.true; otherwise, return false.This approach ensures O(n) time complexity (since we traverse the list a constant number of times) and O(1) extra space (since we only use a few pointers).
Let's consider the linked list: 1 -> 2 -> 2 -> 1
slow moves to the first 2, fast moves to the last 2.fast reaches the end, slow is at the first 2 (the midpoint).2 to 1.1 -> 2 -> 1 -> 2 (with the second half reversed).1 (head) with 1 (start of reversed half) - match.2 with 2 - match.The optimized approach is preferred for large lists and when extra space is restricted.
To determine if a singly linked list is a palindrome, we can efficiently find the midpoint, reverse the second half of the list, and compare both halves node by node. This approach leverages pointer manipulation to avoid extra space, making it both time and space efficient. Restoring the original list is optional but good practice. The elegance of this solution lies in its use of the fast and slow pointer technique and in-place reversal to achieve O(n) time and O(1) space complexity.