In this guide, you will get 234. Palindrome Linked List LeetCode Solution with the best time and space complexity. The solution to Palindrome Linked List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Follow up: Could you do it in O(n) time and O(1) space?
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
234. Palindrome Linked List LeetCode Solution in C++
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
if (fast != nullptr)
slow = slow->next;
slow = reverseList(slow);
while (slow != nullptr) {
if (slow->val != head->val)
return false;
slow = slow->next;
head = head->next;
}
return true;
}
private:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head != nullptr) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
}; /* code provided by PROGIEZ */
234. Palindrome Linked List LeetCode Solution in Java
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null)
slow = slow.next;
slow = reverseList(slow);
while (slow != null) {
if (slow.val != head.val)
return false;
slow = slow.next;
head = head.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
} // code provided by PROGIEZ
234. Palindrome Linked List LeetCode Solution in Python
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
def reverseList(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast:
slow = slow.next
slow = reverseList(slow)
while slow:
if slow.val != head.val:
return False
slow = slow.next
head = head.next
return True # code by PROGIEZ
