Posted on by Kalkicode

# Detect rotational palindrome in doubly linked list

The problem at hand involves detecting rotational palindromes in a doubly linked list. A rotational palindrome is a sequence of elements that remains unchanged when the list is rotated either to the left or right. In other words, if we take a subsection of the linked list and rotate it, the elements in that subsection should still read the same forwards and backwards.

## Problem Statement

Given a doubly linked list, we need to determine whether there exists a rotational palindrome within the list and if so, identify and display the elements of that palindrome.

## Example

``2 <-> 3 <-> 1 <-> 1 <-> 1 <-> 1 <-> 3 <-> 2 <-> 1``

Rotating this list to the right or left by some positions results in:

``1 <-> 1 <-> 3 <-> 2 <-> 1 <-> 2 <-> 3 <-> 1 <-> 1``

As you can see, the rotated sequence "1 1 3 2 1 2 3 1 1" is a palindrome.

## Idea to Solve

The idea to solve this problem involves checking each node in the doubly linked list as a potential starting point for a rotational palindrome. For each starting point, we'll examine its neighboring elements and determine if they form a rotational palindrome.

## Algorithm

1. For each node `node` in the doubly linked list: a. Check if `node.next` exists and if its data is the same as `node.data`. b. If true, call the `isRotationalPalindrome(node)` function to determine if a rotational palindrome starts from `node`.

2. In the `isRotationalPalindrome(front)` function: a. Initialize `reverse` to the previous node of `front` and `forward` to the second next node of `front`. b. Handle cases where `reverse` or `forward` are null by wrapping around to the opposite end of the list. c. While `reverse` and `forward` are not equal and `front` is not equal to `reverse` and `forward` is not equal to `front`: i. Compare the data of `forward` and `reverse`. If they are not equal, return `false`. ii. Update `reverse` to the previous node or the tail if it's null. iii. Update `forward` to the next node or the head if it's null. d. If the loop terminates, return `true`, indicating a rotational palindrome.

3. In the `showResult(front)` function: a. Initialize `node` to `front.next`. If it's null, set `node` to `this.head`. b. Display the elements of the rotational palindrome, handling the circular nature of the list.

4. In the `palindrome()` function: a. Handle cases where the linked list is empty or has only one element. b. Iterate through the linked list and check for potential rotational palindromes using the `isRotationalPalindrome()` function. c. If a palindrome is found, display it using the `showResult()` function.

## Time Complexity

The time complexity of this algorithm mainly depends on the `isRotationalPalindrome()` function, which iterates through the linked list to check for rotational palindromes. In the worst case, it would iterate through the entire list twice, resulting in O(n) time complexity, where n is the number of elements in the linked list. The overall time complexity of the entire algorithm remains O(n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post