Problem Statement

Given a doubly linked list, determine whether it is a palindrome.

A doubly linked list is a palindrome if it reads the same backward as forward, utilizing the previous and next pointers of the nodes.

Examples

1. Example 1:

   • Input: 1 <-> 2 <-> 3 <-> 2 <-> 1
   • Output: true
   • Justification: The list reads the same backward as forward.

2. Example 2:

   • Input: 1 <-> 2 <-> 2 <-> 3
   • Output: false
   • Justification: Reading backward, the list is 3 <-> 2 <-> 2 <-> 1, which is not the same as reading forward.

3. Example 3:

   • Input: 1 <-> 1 <-> 1 <-> 1
   • Output: true
   • Justification: All elements are the same, so the list is a palindrome.

Solution

To determine whether a doubly linked list is a palindrome, we can utilize two pointers approach. Initialize two pointers, one at the start and one at the end of the doubly linked list. Compare the elements at these pointers. If the elements are equal, move the start pointer one step forward and the end pointer one step backward and compare again. If at any point the elements at the pointers are not equal, the list is not a palindrome. Continue this process until the start pointer is greater than or equal to the end pointer. If the loop finishes without finding unequal elements, the list is a palindrome.

Here is the step-by-step solution.

1. Check for Base Cases:

   • If the head of the doubly linked list is null or if there is only one node (head's next is null), return true.

2. Find the Tail Node:

   • Start with the head node and traverse to the end of the list to find the tail node. This is achieved by iterating through the nodes using next pointers until you reach a node where next is null.

3. Initialize Two Pointers:

   • Two pointers are initialized: start at the head of the list and end at the tail of the list.

4. Palindrome Check Loop:

   • The list is traversed from both ends simultaneously towards the middle. In each iteration:
     • Compare the values of the nodes pointed by start and end.
     • If the values are not equal at any point, return false, indicating that the list is not a palindrome.
     • Move start forward (to the next node) and end backward (to the previous node).

5. Return Result:

   • If the loop completes without returning false, it means all mirrored elements in the list are equal. Hence, the function returns true, confirming that the list is a palindrome.

This algorithm is effective because it leverages the nature of a doubly linked list, using both next and previous pointers to compare elements from both ends of the list, reducing the time complexity. As we are not using any additional data structures to store elements of the list and only using constant extra space, it is space-efficient as well.

Algorithm Walkthrough:

• Initialize two pointers: start at the head of the list and end at the tail.
• While the start pointer is less than the end pointer:
  • Compare the values at the start and end pointers.
  • If they are not equal, return false.
  • Move the start pointer one step forward and the end pointer one step backward.
• If the loop finishes without returning, return true, as the list is a palindrome.

Here is the visual representation of the algorithm: