Given head of a singly linked list, check whether linked list values form a palindrome sequence. Return true when forward order and backward order of values match, otherwise return false.
A palindrome linked list reads same from start to end and end to start. Node links remain singly directed, so direct backward traversal is unavailable.
Example 1
Input: head = [1, 2, 2, 1]
Output: true
Explanation: Forward values [1, 2, 2, 1] and backward values [1, 2, 2, 1] are equal.
Example 2
Input: head = [1, 2]
Output: false
Explanation: Forward values [1, 2] and backward values [2, 1] are different.
Brute Force Approach
A stack naturally provides the reverse order of the linked-list values because it follows LIFO (Last In, First Out). Storing every value first allows the second traversal to compare each node from the beginning with its corresponding value from the end, without changing the linked-list structure.
Algorithm
Initialize an empty stack to store the values of the linked-list nodes.
Traverse the linked list from head to tail and push every node's value onto the stack, so the top of the stack represents the value from the end of the list.
Reset the traversal pointer to
head, as the values now need to be compared from the beginning.Pop the top value from the stack and compare it with the current node's value, since corresponding values from both ends must match for a palindrome.
Return
falsewhen any pair of values differs, as a single mismatch proves that the linked list is not a palindrome.Move to the next node and continue the comparison until the entire list has been processed.
Return
truewhen every corresponding pair matches, confirming that the linked list is a palindrome.
Dry Run
palindrome
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; ListNode* next; // Create a new node. ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Check whether the linked list is a palindrome. bool isPalindrome(ListNode* head) { stack<int> values; ListNode* current = head; // Push all node values onto the stack. while (current != nullptr) { values.push(current->data); current = current->next; } current = head; // Compare nodes with values in reverse order. while (current != nullptr) { if (current->data != values.top()) { return false; } values.pop(); current = current->next; } return true; }};Complexity Analysis
Time Complexity: O(N), linked list traversal and mirrored comparisons cover each value at most once.
Space Complexity: O(N), array storage keeps all node values.
Optimal Approach
We find the middle of the linked list using slow and fast pointers. Then, we reverse the second half of the list so that both halves can be compared from left to right.
After reversal, one pointer starts from the head and another starts from the reversed second half. If all corresponding values match, the linked list is a palindrome. Finally, we restore the reversed half to preserve the original linked list structure.
Algorithm
Return
truewhen the linked list is empty or contains only one node, as such a list reads the same from both directions.Use
slowandfastpointers to find the middle of the linked list, sinceslowreaches the midpoint whilefastmoves twice as quickly.Reverse the second half starting after the middle node, as this makes the values from the end accessible in forward traversal for comparison.
Compare nodes from the first half and the reversed second half one by one, since corresponding values from both halves must be equal for the list to be a palindrome.
If any pair of values differs, restore the reversed second half and return
false, as the mismatch proves that the linked list is not a palindrome while restoration preserves the original structure.If all corresponding values match, restore the reversed second half, since the temporary reversal is no longer needed.
Return
true, as every compared pair matched and the linked list is therefore a palindrome.
Dry Run
palindrome second half reversal
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; ListNode* next; ListNode(int value) { data = value; next = nullptr; }};class Solution {private: // Function to reverse linked list links. ListNode* reverseList(ListNode* head) { ListNode* previous = nullptr; ListNode* current = head; // Reverse links one by one. while (current != nullptr) { ListNode* front = current->next; current->next = previous; previous = current; current = front; } return previous; }public: // Function to check palindrome using second half reversal. bool isPalindrome(ListNode* head) { if (head == nullptr || head->next == nullptr) return true; ListNode* slow = head; ListNode* fast = head; // Move slow to middle node. while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } ListNode* secondHead = reverseList(slow->next); ListNode* first = head; ListNode* second = secondHead; // Compare first half and reversed second half. while (second != nullptr) { if (first->val != second->val) { slow->next = reverseList(secondHead); return false; } first = first->next; second = second->next; } slow->next = reverseList(secondHead); return true; }};// Function to create linked list from array.ListNode* createList(vector<int>& arr) { if (arr.empty()) return nullptr; ListNode* head = new ListNode(arr[0]); ListNode* current = head; for (int index = 1; index < (int)arr.size(); index++) { current->next = new ListNode(arr[index]); current = current->next; } return head;}// Driver code.int main() { vector<int> arr = {1, 2, 2, 1}; ListNode* head = createList(arr); Solution sol; cout << (sol.isPalindrome(head) ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(N), middle search, reversal, comparison, and restoration are linear combined.
Space Complexity: O(1), only a fixed number of pointers are used.
Interview follow-up Questions
Yes. Second half reversal compares mirrored nodes using constant extra memory.
Be the first to add a comment.