Posted on by Kalkicode

# Check if palindrome exists in doubly linked list

This article addresses an intriguing algorithmic challenge: detecting whether a given doubly linked list is a palindrome or not. We will provide a clear problem statement, illustrate the concept with an example, propose an approach to solve the problem, present standard pseudocode, detail the algorithm's implementation, explain the output, and analyze the time complexity. The explanation will be presented in a straightforward and comprehensible manner.

## Problem Statement

The task is to determine whether a given doubly linked list forms a palindrome or not. A palindrome is a sequence that reads the same forwards as it does backward. In the context of a linked list, we need to check if the sequence of node values from the head to tail is the same as from the tail to head.

## Illustrative Example

Consider the following doubly linked list:

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

This linked list is a palindrome since the sequence reads the same both ways. Conversely, if we have:

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

In this case, the linked list is not a palindrome because the sequences don't match when reversed.

## Algorithmic Approach

1. Initialize pointers `first` and `last` to the head and tail of the linked list, respectively.
2. Traverse the linked list while comparing the node values of `first` and `last`.
3. If the values are different, the linked list is not a palindrome.
4. If `first` and `last` meet or cross paths, the linked list is a palindrome.
5. Continue traversing until the pointers meet or cross.

## Pseudocode

``````isPalindrome():
return false
Initialize first = head, last = tail

Loop until first and last pointers meet or cross:
Compare the node values of first and last
If values are different, return false

Move first to the next node
Move last to the previous node

If first and last meet or cross, return true (linked list is palindrome)
Otherwise, return false

Main():
Initialize a doubly linked list (dll)
Insert nodes into the linked list

Display the list
Check if the list is a palindrome
Display the result

Insert a new element into the linked list
Display the updated list
Check if the updated list is a palindrome
Display the result``````

## Time Complexity Analysis

• The `isPalindrome` function iterates through the linked list once, performing constant-time operations per iteration. Thus, its time complexity is O(n), where n is the number of nodes in the list.

## 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