Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Copying values into an array and comparing is O(n) extra space.
  2. 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

  1. 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");
    }
}

Solve Palindrome Linked List online · All practice problems