Practice › Linked List
Palindrome Linked List
Easy · Linked List · Asked at Amazon, Microsoft, Adobe, TCS, Infosys
Print YES if the list reads the same forwards and backwards, otherwise NO.
Input
First line: n. Second line: the n node values from head to tail.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
O(1) extra space: find the middle, reverse the second half, compare.
Example 1
Input
4 1 2 2 1
Output
YES
Example 2
Input
2 1 2
Output
NO
Hints
- Copying values into an array and comparing is O(n) extra space.
- For O(1) space: find the middle with slow/fast pointers, reverse the second half, then compare it with the first half node by node.
Approach
- Find the middle with slow/fast pointers. 2) Reverse the list from slow onwards. 3) Walk one pointer from the head and one from the reversed half's head, comparing values until the second one runs out. Any mismatch means NO. In production code you'd reverse the second half back afterwards to restore the list.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next;
Node(long long v) : val(v), next(nullptr) {}
};
int main() {
int n;
cin >> n;
Node dummy(0), *tail = &dummy;
for (int i = 0; i < n; i++) {
long long v;
cin >> v;
tail = tail->next = new Node(v);
}
Node *head = dummy.next, *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
Node *prev = nullptr; // reverse the second half
while (slow) {
Node *next = slow->next;
slow->next = prev;
prev = slow;
slow = next;
}
bool ok = true;
for (Node *a = head, *b = prev; b; a = a->next, b = b->next)
if (a->val != b->val) { ok = false; break; }
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
data = sys.stdin.read().split()
n = int(data[0])
head = None
for v in reversed(data[1 : n + 1]):
head = Node(int(v), head)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None # reverse the second half
while slow:
nxt = slow.next
slow.next = prev
prev, slow = slow, nxt
ok, a, b = True, head, prev
while b:
if a.val != b.val:
ok = False
break
a, b = a.next, b.next
print("YES" if ok else "NO")Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node dummy = new Node(0), tail = dummy;
for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
Node head = dummy.next, slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Node prev = null; // reverse the second half
while (slow != null) {
Node next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
boolean ok = true;
for (Node a = head, b = prev; b != null; a = a.next, b = b.next)
if (a.val != b.val) { ok = false; break; }
System.out.println(ok ? "YES" : "NO");
}
}