Opening the reading…
Opening the reading…
LINKED LIST › LINKED LIST (PART 1)
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →A palindrome has matching values at equal distances from the two ends. An array can compare those ends directly, but a singly linked list cannot move backward from its tail. The useful replacement is to make the second half point toward its own beginning: once that suffix is reversed, walking forward through it is equivalent to walking backward through the original list.
The slow pointer reaches the midpoint while the fast pointer moves twice as quickly. For an even-length list, slow stops at the end of the first half; for an odd-length list, it stops on the middle node. Starting the reversal at slow->next skips that unpaired middle value, so both sides contribute the same number of values to the comparison.
| MEASURE | BOUND | WHY |
|---|---|---|
| Time | O(n) | The midpoint walk, reversal walk, and comparison walk each advance through disjoint or bounded portions of the list. Each node is examined a constant number of times, so their total work is at most a constant multiple of n. |
| Space | O(1) extra | Only a fixed number of ListNode pointers are stored; the list links themselves are reused rather than copied. The required output is one boolean and is excluded from working memory. The bound stays O(1) even for the worst-shaped input, a list containing n nodes in one chain. |
#include <cstddef>
using namespace std;
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = nullptr;
ListNode* curr = slow->next;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
ListNode* left = head;
ListNode* right = prev;
while (right != nullptr) {
if (left->val != right->val) {
return false;
}
left = left->next;
right = right->next;
}
return true;
}
};The two conditions in the midpoint loop are deliberate. Using fast->next and fast->next->next keeps slow one node before the suffix for even lengths and on the middle node for odd lengths. The comparison only follows right, so both cases compare exactly the mirrored pairs and never need a special middle-value branch.
The main solution changes the links in the second half and returns as soon as it finds a mismatch. That is valid when the problem only asks for a boolean, but another component may expect the input list to remain unchanged. A reasonable engineering alternative reverses the suffix back before returning. It uses the same O(1) extra space and O(n) time bound, with one additional linear pass.
#include <cstddef>
using namespace std;
class Solution {
private:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode* slow = head;
ListNode* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* secondStart = slow->next;
ListNode* reversed = reverseList(secondStart);
bool result = true;
ListNode* left = head;
ListNode* right = reversed;
while (right != nullptr) {
if (left->val != right->val) {
result = false;
break;
}
left = left->next;
right = right->next;
}
reverseList(reversed);
return result;
}
};