Check if LL is palindrome or not
Linked-List
FAQs (Medium)
Medium
- Linked list operations like this are used in many software applications that require dynamic memory management
- In particular, the concept of checking if a linked list is a palindrome has a fun association with text processing software
- For example, in apps that check if a string of text is a palindrome (a word, phrase, or sequence that reads the same backwards as forwards, like "madam" or "12321"), a linked list can be utilized to store characters or digits in sequence and then used to validate the palindrome property
- This type of string validation is practical in areas such as DNA sequencing where bioinformatics software often needs to check palindromic sequences
- In more general terms, this problem signifies the usefulness and versatility of linked lists in managing and manipulating data
Given the head of a singly linked list representing a positive integer number. Each node of the linked list represents a digit of the number, with the 1st node containing the leftmost digit of the number and so on. Check whether the linked list values form a palindrome or not. Return true if it forms a palindrome, otherwise, return false.
A palindrome is a sequence that reads the same forward and backwards.
Examples:
Input: head -> 3 -> 7 -> 5 -> 7 -> 3
Output: true
Explanation: 37573 is a palindrome.
Input: head -> 1 -> 1 -> 2 -> 1
Output: false
Explanation: 1121 is not a palindrome.
Input: head -> 9 -> 9 -> 9 -> 9
Constraints
- 1 <= number of nodes in the Linked List <= 105
- 0 <= ListNode.val <= 9
- The number represented does not contain any leading zeroes.
Hints
- A brute-force approach would involve: Storing all the digits in an array (O(n) space). Checking if the array is a palindrome (O(n) time). Drawback: Uses O(n) extra space, violating in-place constraints.
- To check for a palindrome in O(n) time and O(1) space, we use the slow and fast pointer technique: Find the middle of the list using two pointers (slow and fast). Reverse the second half of the linked list. Compare the first half with the reversed second half.
Company Tags
Intel
Seagate Technology
Bloomberg
Cloudflare
Johnson & Johnson
Teladoc Health
Micron Technology
Lyft
Activision Blizzard
Shopify
Freshworks
MongoDB
Alibaba
Oracle
DoorDash
Boston Consulting Group
PayPal
Robinhood
Morgan Stanley
Roche
Optum
Snowflake
Zynga
Etsy
PwC
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition
A simple way to determine if a given linked list is a palindrome is to use an additional data structure to temporarily store the node values. We can utilize a stack for this purpose. As we traverse the linked list, we push each node's value onto the stack, which stores the values in reverse order. After traversing the entire list, we traverse it again and compare each node's value with the values popped from the top of the stack. If all values match, the linked list is a palindrome.
Approach
- Initialize: Begin by creating an empty stack. This stack will help us temporarily store the nodes' values as we traverse the linked list.
- Traverse and Store: Traverse the linked list using a temporary pointer `temp`. As we move through each node, push its value onto the stack. This action stacks the values in reverse order—starting from the head to the tail of the linked list.
- Comparison: Reset the `temp` pointer back to the head of the linked list after storing all values. While the stack is not empty:
- Pop the top value from the stack.
- Compare this value with the value at the current `temp` node.
- If they match, move `temp` to the next node and continue the comparison.
- If any value does not match during this traversal, conclude that the linked list is not a palindrome and return false.
- Palindrome Check: If all values match until the `temp` pointer reaches the end of the linked list, conclude that the linked list is a palindrome and return true.
This approach uses a stack to reverse the order of values temporarily, allowing efficient comparison to check if the linked list maintains symmetry both forwards and backwards.
Dry Run
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
val = 0;
next = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
class Solution {
public:
bool isPalindrome(ListNode* head) {
/*Create an empty stack
to store values*/
stack<int> st;
/*Initialize temporary pointer
to the head of the linked list*/
ListNode* temp = head;
/*Traverse the linked list
and push values onto the stack*/
while (temp != NULL) {
/*Push the data from
the current node onto the stack*/
st.push(temp->val);
// Move to the next node
temp = temp->next;
}
/*Reset temporary pointer
back to the head of
the linked list*/
temp = head;
/*Compare values by popping
from the stack and checking
\against linked list nodes*/
while (temp != NULL) {
if (temp->val != st.top()) {
/*If values don't match,
it's not a palindrome*/
return false;
}
// Pop the value
st.pop();
/*Move to the next node
in the linked list*/
temp = temp->next;
}
/*If all values match,
it's a palindrome*/
return true;
}
};
/*Function to print the linked list*/
void printLinkedList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
/*Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)*/
ListNode* head = new ListNode(1);
head->next = new ListNode(5);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(5);
head->next->next->next->next = new ListNode(1);
// Print the original linked list
cout << "Original Linked List: ";
printLinkedList(head);
// Check if the linked list is a palindrome
Solution solution;
if (solution.isPalindrome(head)) {
cout << "The linked list is a palindrome." << endl;
} else {
cout << "The linked list is not a palindrome." << endl;
}
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
import java.util.*;
// Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
public boolean isPalindrome(ListNode head) {
/*Create an empty stack
to store values*/
Stack<Integer> stack = new Stack<>();
/*Initialize temporary pointer
to the head of the linked list*/
ListNode temp = head;
/*Traverse the linked list
and push values onto the stack*/
while (temp != null) {
/*Push the data from
the current node onto the stack*/
stack.push(temp.val);
// Move to the next node
temp = temp.next;
}
/*Reset temporary pointer
back to the head of
the linked list*/
temp = head;
/*Compare values by popping
from the stack and checking
against linked list nodes*/
while (temp != null) {
if (temp.val != stack.pop()) {
/*If values don't match,
it's not a palindrome*/
return false;
}
/*Move to the next node
in the linked list*/
temp = temp.next;
}
/*If all values match,
it's a palindrome*/
return true;
}
/*Function to print the linked list*/
public static void printLinkedList(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
/*Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)*/
ListNode head = new ListNode(1);
head.next = new ListNode(5);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(1);
// Print the original linked list
System.out.print("Original Linked List: ");
printLinkedList(head);
// Check if the linked list is a palindrome
Solution solution = new Solution();
if (solution.isPalindrome(head)) {
System.out.println("The linked list is a palindrome.");
} else {
System.out.println("The linked list is not a palindrome.");
}
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
# Definition of singly linked list:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head):
# Create an empty stack
stack = []
# Initialize temporary pointer
temp = head
# Traverse the linked list
while temp is not None:
# Push the data from
# the current node onto the stack
stack.append(temp.val)
# Move to the next node
temp = temp.next
# Reset temporary pointer
# back to the head of the
# linked list
temp = head
# Compare values by popping from the
# stack and checking against linked list nodes
while temp is not None:
if temp.val != stack.pop():
# If values don't match,
# it's not a palindrome
return False
# Move to the next node
# in the linked list
temp = temp.next
# If all values match,
# it's a palindrome
return True
# Function to print the linked list
def print_linked_list(head):
temp = head
while temp is not None:
print(temp.val, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
# Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)
head = ListNode(1)
head.next = ListNode(5)
head.next.next = ListNode(2)
head.next.next.next = ListNode(5)
head.next.next.next.next = ListNode(1)
# Print the original linked list
print("Original Linked List: ", end="")
print_linked_list(head)
# Check if the linked list is a palindrome
solution = Solution()
if solution.isPalindrome(head):
print("The linked list is a palindrome.")
else:
print("The linked list is not a palindrome.")
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
// Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
isPalindrome(head) {
/*Create an empty stack
to store values*/
const stack = [];
/*Initialize temporary
pointer to the head
of the linked list*/
let temp = head;
/* Traverse the linked list
and push values onto the stack*/
while (temp !== null) {
/* Push the data from the
current node onto the stack*/
stack.push(temp.val);
// Move to the next node
temp = temp.next;
}
/*Reset temporary
pointer back to the
head of the linked list*/
temp = head;
/*Compare values by popping
from the stack and checking
against linked list nodes*/
while (temp !== null) {
if (temp.val !== stack.pop()) {
/*If values don't match,
it's not a palindrome*/
return false;
}
/*Move to the next node
in the linked list*/
temp = temp.next;
}
/*If all values match,
it's a palindrome*/
return true;
}
}
// Function to print the linked list
function printLinkedList(head) {
let temp = head;
while (temp !== null) {
process.stdout.write(temp.val + " ");
temp = temp.next;
}
console.log();
}
// Main function to test the code
(function main() {
// Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)
let head = new ListNode(1);
head.next = new ListNode(5);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(1);
// Print the original linked list
process.stdout.write("Original Linked List: ");
printLinkedList(head);
// Check if the linked list is a palindrome
const solution = new Solution();
if (solution.isPalindrome(head)) {
console.log("The linked list is a palindrome.");
} else {
console.log("The linked list is not a palindrome.");
}
})();
Complexity Analysis
Time Complexity: O(2xN) because we need to traverse the linked list twice: once to push the values onto the stack and once more to pop the values and compare them with the nodes in the linked list. Here, N represents the number of nodes in the linked list. Even though it's O(2xN), it effectively simplifies to O(N). Space Complexity: O(N) We use a stack to store the values of the linked list. In the worst-case scenario, the stack will hold all N values from the linked list, essentially storing the entire list.Intuition
The previous approach uses O(N) additional space, which can be avoided by reversing only half of the linked list and comparing the first and second halves. If they match, reverse the portion that was originally reversed, and then return true; otherwise, return false. To implement this, we need to reverse the second half and compare it with the first half in phases. The first step is to divide the linked list into two halves by finding the middle node using the Tortoise and Hare Algorithm.
Approach
Find the middle of the linked list using the Tortoise and Hare Algorithm, then reverse the second half of the list and compare it with the first half. If all values match, the list is a palindrome; otherwise, it is not. This approach ensures that the list is correctly checked without using additional space beyond the stack space used during recursion.
Detailed Steps to Check Palindrome in a Linked ListCheck Base Case: If the linked list is empty or has only one node, it is a palindrome by definition. Return true.
Find the Middle: Initialize two pointers, ‘slow’ and ‘fast’. Use the Tortoise and Hare Algorithm where ‘slow’ moves one step at a time and ‘fast’ moves two steps at a time. Continue until ‘fast’ reaches the end or the second last node. The ‘slow’ pointer will be at the middle.
Reverse Second Half: Reverse the second half of the linked list starting from the node after the middle (‘slow->next’). Use a function to reverse the linked list and return the head of the reversed list.
Initialize Pointers for Comparison: Create two pointers, ‘first’ pointing to the head of the linked list and ‘second’ pointing to the head of the reversed second half.
Compare Halves: Compare the data values of nodes from both halves. If any values do not match, return false. Move both ‘first’ and ‘second’ pointers through their respective halves, comparing values until one of them reaches the end.
Restore Original List: After comparison, reverse the second half back to its original state and reattach it to the first half. If all values matched, return true. If not, return false.
Dry Run
For Linked List with Even Number of Nodes
For Linked List with Odd Number of Nodes
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
val = 0;
next = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
class Solution {
private:
/*Function to reverse a linked list
using the recursive approach*/
ListNode* reverseLinkedList(ListNode* head) {
/* Check if the list is empty
or has only one node*/
if (head == NULL || head->next == NULL) {
/*No change is needed;
return the current head*/
return head;
}
/*Reverse the remaining
part of the list and get the new head*/
ListNode* newHead = reverseLinkedList(head->next);
/*Store the next node in 'front'
to reverse the link*/
ListNode* front = head->next;
/*Update the 'next' pointer of 'front' to
point to the current head, effectively
reversing the link direction*/
front->next = head;
/* Set the 'next' pointer of the
current head to 'null' to
break the original link*/
head->next = NULL;
/*Return the new head obtained
from the recursion*/
return newHead;
}
public:
bool isPalindrome(ListNode* head) {
/*Check if the linked list is empty
or has only one node*/
if (head == NULL || head->next == NULL) {
// It's a palindrome by definition
return true;
}
/* Initialize two pointers, slow and fast,
to find the middle of the linked list*/
ListNode* slow = head;
ListNode* fast = head;
/* Traverse the linked list to find the
middle using slow and fast pointers*/
while (fast->next != NULL && fast->next->next != NULL) {
// Move slow pointer one step
slow = slow->next;
// Move fast pointer two steps
fast = fast->next->next;
}
/*Reverse the second half of the
linked list starting from the middle*/
ListNode* newHead = reverseLinkedList(slow->next);
// Pointer to the first half
ListNode* first = head;
// Pointer to the reversed second half
ListNode* second = newHead;
while (second != NULL) {
/*Compare data values of
nodes from both halves.
If values do not match,
the list is not a palindrome*/
if (first->val != second->val) {
/*Reverse the second half
back to its original state*/
reverseLinkedList(newHead);
// Not a palindrome
return false;
}
// Move the first pointer
first = first->next;
// Move the second pointer
second = second->next;
}
/*Reverse the second half
back to its original state*/
reverseLinkedList(newHead);
// Linked List is a palindrome
return true;
}
};
/*Function to print the linked list*/
void printLinkedList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
/*Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)*/
ListNode* head = new ListNode(1);
head->next = new ListNode(5);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(5);
head->next->next->next->next = new ListNode(1);
// Print the original linked list
cout << "Original Linked List: ";
printLinkedList(head);
// Check if the linked list is a palindrome
Solution solution;
if (solution.isPalindrome(head)) {
cout << "The linked list is a palindrome." << endl;
} else {
cout << "The linked list is not a palindrome." << endl;
}
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
import java.util.*;
class ListNode {
int val;
ListNode next;
// Constructor with no parameters
ListNode() {
val = 0;
next = null;
}
// Constructor with one parameter
ListNode(int data1) {
val = data1;
next = null;
}
// Constructor with two parameters
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
/*Function to reverse a linked list
using the recursive approach*/
private ListNode reverseLinkedList(ListNode head) {
/* Check if the list is empty
or has only one node*/
if (head == null || head.next == null) {
/*No change is needed;
return the current head*/
return head;
}
/*Reverse the remaining
part of the list and get the new head*/
ListNode newHead = reverseLinkedList(head.next);
/*Store the next node in 'front'
to reverse the link*/
ListNode front = head.next;
/*Update the 'next' pointer of 'front' to
point to the current head, effectively
reversing the link direction*/
front.next = head;
/* Set the 'next' pointer of the
current head to 'null' to
break the original link*/
head.next = null;
/*Return the new head obtained
from the recursion*/
return newHead;
}
public boolean isPalindrome(ListNode head) {
/*Check if the linked list is empty
or has only one node*/
if (head == null || head.next == null) {
// It's a palindrome by definition
return true;
}
/* Initialize two pointers, slow and fast,
to find the middle of the linked list*/
ListNode slow = head;
ListNode fast = head;
/* Traverse the linked list to find the
middle using slow and fast pointers*/
while (fast.next != null && fast.next.next != null) {
// Move slow pointer one step
slow = slow.next;
// Move fast pointer two steps
fast = fast.next.next;
}
/*Reverse the second half of the
linked list starting from the middle*/
ListNode newHead = reverseLinkedList(slow.next);
// Pointer to the first half
ListNode first = head;
// Pointer to the reversed second half
ListNode second = newHead;
while (second != null) {
/*Compare data values of
nodes from both halves.
If values do not match,
the list is not a palindrome*/
if (first.val != second.val) {
/*Reverse the second half
back to its original state*/
reverseLinkedList(newHead);
// Not a palindrome
return false;
}
// Move the first pointer
first = first.next;
// Move the second pointer
second = second.next;
}
/*Reverse the second half
back to its original state*/
reverseLinkedList(newHead);
// Linked List is a palindrome
return true;
}
}
class Main {
static void printLinkedList(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
/*Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)*/
ListNode head = new ListNode(1);
head.next = new ListNode(5);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(1);
// Print the original linked list
System.out.print("Original Linked List: ");
printLinkedList(head);
// Check if the linked list is a palindrome
Solution solution = new Solution();
if (solution.isPalindrome(head)) {
System.out.println("The linked list is a palindrome.");
} else {
System.out.println("The linked list is not a palindrome.");
}
}
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
# Definition of singly linked list:
class ListNode:
def __init__(self, data1=0, next1=None):
self.val = data1
self.next = next1
class Solution:
# Function to reverse a linked list
# using the recursive approach
def reverseLinkedList(self, head):
# Check if the list is empty
# or has only one node
if head is None or head.next is None:
# No change is needed;
# return the current head
return head
# Reverse the remaining
# part of the list and get the new head
newHead = self.reverseLinkedList(head.next)
# Store the next node in 'front'
# to reverse the link
front = head.next
# Update the 'next' pointer of 'front' to
# point to the current head, effectively
# reversing the link direction
front.next = head
# Set the 'next' pointer of the
# current head to 'null' to
# break the original link
head.next = None
# Return the new head obtained
# from the recursion
return newHead
def isPalindrome(self, head):
# Check if the linked list is empty
# or has only one node
if head is None or head.next is None:
# It's a palindrome by definition
return True
# Initialize two pointers, slow and fast,
# to find the middle of the linked list
slow = head
fast = head
# Traverse the linked list to find the
# middle using slow and fast pointers
while fast.next is not None and fast.next.next is not None:
# Move slow pointer one step
slow = slow.next
# Move fast pointer two steps
fast = fast.next.next
# Reverse the second half of the
# linked list starting from the middle
newHead = self.reverseLinkedList(slow.next)
# Pointer to the first half
first = head
# Pointer to the reversed second half
second = newHead
while second is not None:
# Compare data values of
# nodes from both halves.
# If values do not match,
# the list is not a palindrome
if first.val != second.val:
# Reverse the second half
# back to its original state
self.reverseLinkedList(newHead)
# Not a palindrome
return False
# Move the first pointer
first = first.next
# Move the second pointer
second = second.next
# Reverse the second half
# back to its original state
self.reverseLinkedList(newHead)
# Linked List is a palindrome
return True
# Function to print the linked list
def printLinkedList(head):
temp = head
while temp is not None:
print(temp.val, end=" ")
temp = temp.next
print()
if __name__ == "__main__":
# Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)
head = ListNode(1)
head.next = ListNode(5)
head.next.next = ListNode(2)
head.next.next.next = ListNode(5)
head.next.next.next.next = ListNode(1)
# Print the original linked list
print("Original Linked List: ", end="")
printLinkedList(head)
# Check if the linked list is a palindrome
solution = Solution()
if solution.isPalindrome(head):
print("The linked list is a palindrome.")
else:
print("The linked list is not a palindrome.")123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137
// Definition of singly linked list:
class ListNode {
constructor(data1 = 0, next1 = null) {
this.val = data1;
this.next = next1;
}
}
class Solution {
/*Function to reverse a linked list
using the recursive approach*/
reverseLinkedList(head) {
/* Check if the list is empty
or has only one node*/
if (head === null || head.next === null) {
/*No change is needed;
return the current head*/
return head;
}
/*Reverse the remaining
part of the list and get the new head*/
let newHead = this.reverseLinkedList(head.next);
/*Store the next node in 'front'
to reverse the link*/
let front = head.next;
/*Update the 'next' pointer of 'front' to
point to the current head, effectively
reversing the link direction*/
front.next = head;
/* Set the 'next' pointer of the
current head to 'null' to
break the original link*/
head.next = null;
/*Return the new head obtained
from the recursion*/
return newHead;
}
isPalindrome(head) {
/*Check if the linked list is empty
or has only one node*/
if (head === null || head.next === null) {
// It's a palindrome by definition
return true;
}
/* Initialize two pointers, slow and fast,
to find the middle of the linked list*/
let slow = head;
let fast = head;
/* Traverse the linked list to find the
middle using slow and fast pointers*/
while (fast.next !== null && fast.next.next !== null) {
// Move slow pointer one step
slow = slow.next;
// Move fast pointer two steps
fast = fast.next.next;
}
/*Reverse the second half of the
linked list starting from the middle*/
let newHead = this.reverseLinkedList(slow.next);
// Pointer to the first half
let first = head;
// Pointer to the reversed second half
let second = newHead;
while (second !== null) {
/*Compare data values of
nodes from both halves.
If values do not match,
the list is not a palindrome*/
if (first.val !== second.val) {
/*Reverse the second half
back to its original state*/
this.reverseLinkedList(newHead);
// Not a palindrome
return false;
}
// Move the first pointer
first = first.next;
// Move the second pointer
second = second.next;
}
/*Reverse the second half
back to its original state*/
this.reverseLinkedList(newHead);
// Linked List is a palindrome
return true;
}
}
// Function to print the linked list
function printLinkedList(head) {
let temp = head;
while (temp !== null) {
process.stdout.write(temp.val + " ");
temp = temp.next;
}
console.log();
}
(function main() {
/*Create a linked list with values 1, 5, 2, 5, and 1 (15251, a palindrome)*/
let head = new ListNode(1);
head.next = new ListNode(5);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(1);
// Print the original linked list
process.stdout.write("Original Linked List: ");
printLinkedList(head);
// Check if the linked list is a palindrome
let solution = new Solution();
if (solution.isPalindrome(head)) {
console.log("The linked list is a palindrome.");
} else {
console.log("The linked list is not a palindrome.");
}
})();
Complexity Analysis
Time Complexity: O(2xN) The algorithm involves traversing the linked list twice. The first traversal finds the middle and reverses the second half, while the second traversal compares elements from both halves. Since each traversal covers N/2 elements, the total time complexity is O(N/2 + N/2 + N/2 + N/2), which simplifies to O(2N), ultimately reducing to O(N).
Space Complexity: O(1) This approach uses a constant amount of additional space, regardless of the linked list's size. It does not require any extra data structures that depend on the input size, resulting in a space complexity of O(1).
Frequently Occurring Doubts
Q: Why do we reverse only the second half instead of the full list?
A: We only need to check the latter half against the first half. This keeps the process in-place (O(1) space).
Q: Why do we restore the list after checking?
A: In interview settings, modifying input structure might be disallowed. If restoration isn’t required, skip this step.
Interview Followup Questions
Q: What if the list was circular?
A: Find the midpoint using slow-fast pointers, then break the cycle temporarily.
Q: Can this be solved recursively?
A: Yes, but recursion uses O(n) stack space, making it less efficient.
Notes
Code
✅ Testcase
Input: {'nums': '[3, 7, 5, 7, 3]'}
Expected:
true
true
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[1, 1, 2, 1]'}
Expected:
false
false
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[9, 9, 9, 9]'}
Expected:
true
true
Actual: -
Time: -
sec
Status: Waiting