Problem

Determine whether a doubly linked list is a palindrome.

Definition

Palindrome Definition

Examples

Example 1

1
2
3

Input: 1 <-> 4 <-> 3 <-> 4 <-> 1
Output: True
Explanation: The list reads the same forward and backward.

Example 2

1
2
3

Input: 1 <-> 4
Output: False
Explanation: The list reads 1 -> 4 forward and 4 -> 1 backward.

Follow up

What if it’s singly linked? - Refer - Palindrome Linked List

Solution

Method 1 - Two Pointer Technique

To check if a linked list is a palindrome, one way is to use a two-pointer technique: advancing one pointer to the end, then comparing values from both ends towards the center. For a doubly linked list, this process is straightforward because we have backward pointers. For a singly linked list, we can use a two-pass approach: first copying the values to an array and then checking the array for a palindrome.

Here is the approach:

  1. Initialize two pointers: left at the head and right at the tail.
  2. Move these pointers towards the center, comparing the values they point to at each step.
  3. If all values match, the list is a palindrome.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class DoublyListNode {
    int val;
    DoublyListNode next;
    DoublyListNode prev;
    DoublyListNode(int x) { val = x; }
}

public class Solution {
    public boolean isPalindrome(DoublyListNode head) {
        if (head == null) return true;
        
        DoublyListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        
        DoublyListNode left = head;
        DoublyListNode right = tail;
        
        while (left != right && left.prev != right) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.prev;
        }
        
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        DoublyListNode node1 = new DoublyListNode(1);
        DoublyListNode node2 = new DoublyListNode(4);
        DoublyListNode node3 = new DoublyListNode(3);
        DoublyListNode node4 = new DoublyListNode(4);
        DoublyListNode node5 = new DoublyListNode(1);
        
        node1.next = node2;
        node2.prev = node1;
        node2.next = node3;
        node3.prev = node2;
        node3.next = node4;
        node4.prev = node3;
        node4.next = node5;
        node5.prev = node4;
        
        System.out.println(solution.isPalindrome(node1)); // Output: true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class DoublyListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class Solution:
    def isPalindrome(self, head: DoublyListNode) -> bool:
        if not head:
            return True

        tail = head
        while tail.next:
            tail = tail.next

        left, right = head, tail
        while left != right and left.prev != right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.prev

        return True

# Example usage
node1 = DoublyListNode(1)
node2 = DoublyListNode(4)
node3 = DoublyListNode(3)
node4 = DoublyListNode(4)
node5 = DoublyListNode(1)

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
node4.next = node5
node5.prev = node4

solution = Solution()
print(solution.isPalindrome(node1))  # Output: True

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes (single pass with two pointers).
  • 🧺 Space complexity: O(n) where n is the number of nodes (single pass to copy values, one more pass to check palindrome).