The challenge
Decide whether a list reads the same forward and backward while restoring its original structure.
The input is acyclic. Empty and single-node lists count as palindromes.
Example
[1, 2, 2, 1] → true; [1, 2, 3] → false.
Use the walkthrough below to inspect the input and each state change.
See Palindrome, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 2 | A3 |
| A3 | 2 | A4 |
| A4 | 1 | null |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 2 (A2) → 2 (A3) → 1 (A4); parameters: {}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Only the second half needs reversing; comparing corresponding nodes is then a forward walk.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prev
def is_palindrome(head):
if head is None or head.next is None:
return True
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = reverse(slow.next)
a, b = head, second
matches = True
while b:
if a.val != b.val:
matches = False
a, b = a.next, b.next
slow.next = reverse(second)
return matches
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* reverse(Node* head) {
Node* prev = nullptr;
while (head) {
Node* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
bool is_palindrome(Node* head) {
if (!head || !head->next) return true;
Node* slow = head;
Node* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
Node* second = reverse(slow->next);
Node* a = head;
Node* b = second;
bool matches = true;
while (b) {
if (a->val != b->val) matches = false;
a = a->next;
b = b->next;
}
slow->next = reverse(second);
return matches;
}