Palindrome Linked List Problem Statement:

Given a singly linked list, check whether it is a palindrome or not.

Example One

{
"head": [0, 2, 4, 4, 2, 0]
}

Output

1

Example Two

{
"head": [12, 2, 1]
}

Output:

0

Notes

A palindrome is a sequence that reads the same backward as forward.

Constraints:

• 1 <= length of the list <= 105
• -109 <= node values <= 109

We provided a naive and efficient solution. Our main motive in both the solutions will be to compare the first half of the linked list with the reversed second half of the linked list.

Throughout this editorial, we will refer to the length of the linked list as n.

Palindrome Linked List Solution 1: Naive Solution Using Stack

In the naive approach, we will use a stack. Stack is a linear data structure that stores elements in LIFO (Last-In-First-Out) order. The last element which we pushed into the stack will be the first to be popped out.

So, we will traverse the linked list and push all of its elements into the stack. The nodes will now be popped out in the reverse order of the linked list. Now, once all the elements are pushed into the stack, we will traverse the linked list again and perform the following operation:

At every iteration, we will pop out an element from the stack and will compare it with the current node value. The i-th iteration of this process will be comparing the value of i-th node from the beginning and i-th node from the end of the linked list. If the popped element is not equal to the value of the current node, we will return false, otherwise, we will continue after moving the current node one step ahead.

If we complete the traversal of the linked list without any mismatch, it means the linked list is a palindrome, and we will finally return true.

Note: We can optimize the above solution a little. Instead of making n number of comparisons by traversing the full stack, we can stop after making n/2 number of comparisons. Our main motive is to compare the first and the second half of the linked list, and we will achieve this in the first n/2 comparisons. The next n/2 comparisons will compare the second and first half of the linked list.

Time Complexity

O(n): We will be traversing each node at most twice.

Auxiliary Space Used

O(n): We will require a stack of size n to store the elements of the linked list.

Space Complexity

O(n)

Space used for input: O(n)

Auxiliary space used: O(n)

Space used for output: O(1)

So, total space complexity: O(n).

Know how to find all Palindromic Decompositions of a Given String.

Code for Palindrome Linked List Solution 1: Naive Solution Using Stack

/*
   Asymptotic complexity in terms of length of the input linked list `n`:
   * Time: O(n).
   * Auxiliary space: O(n).
   * Total space: O(n).
   */
   static Boolean is_palindrome(LinkedListNode head) {
       if (head == null || head.next == null) {
           return true;
       }
       LinkedListNode dummy_node = head;
       Stack stack = new Stack();
       while (dummy_node != null) {
           stack.add(dummy_node.value);
           dummy_node = dummy_node.next;
       }
       dummy_node = head;
       /*
       In each iteration, we will pop-out element from the stack and will compare it
       with the value of the current node.
       */
       while (dummy_node != null && (!stack.isEmpty())) {
           if (dummy_node.value != stack.pop().intValue()) {
               return false;
           }
           dummy_node = dummy_node.next;
       }
       return true;
   }

Palindrome Linked List Solution 2: Efficient Solution Using Reverse List

In the efficient approach, we will start by finding the middle element of the linked list (using the hare and tortoise approach). Then we will reverse the second half (linked list after the middle node) of the linked list and compare both halves for equality. Let us try to understand this with the help of an example:

Suppose we have the following linked list:

Find the middle node of the linked list: To find the middle element, we will use two pointers, slow and fast. We will move the slow pointer by one distance and the fast pointer by two distances. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.

Step 1: Initialize slow and fast.

Step 2: Move slow by one distance and fast by two distances, until fast.next != null and fast.next.next != null.

Step 3:

Step 4: We can not move fast further, so we stop. Now, slow represents the middle node of the linked list.

Reverse the second half: To reverse a list, we will just reverse the directions of reference pointers. To do so, we will maintain three-pointers. Initialize three-pointers, previous_node as null, current_node as head, and next as null. Now, we will traverse through the list, and in every iteration, we will perform the following operation:

Change the next pointer to current_node.next, current_node.next to previous_node and previous_node to next.

Step 1: Initialize current_node by node next to mid_node, previous_node by null, and next by null.

Step 2: Now, make sure that next should point to the current_node.next.

Step 3: Disconnect the current_node from next and connect it with the previous_node.

Step 4: Now, make sure that the previous_node should point to the current_node.

Step 5: Now, make sure that current_node should point to next.

Step 6: Repeat the above steps until the complete second part is reversed. The linked list after reversing the second half will look like this:

Compare both halves: Now, we will compare both the halves using two pointers, the first pointer pointing to the head node and the second pointer pointing to the node present next to the middle node. Now we will traverse through both the halves. If we find any mismatch, we return false else, the list is a palindrome, and we return true.

Step 1: Make sure that mid_node points to the head of the reversed list.

Step 2: Now, we will traverse through both halves. If we find any mismatch, we return.

Step 3:

Step 4: We completed traversing both halves without any mismatch. It means the list is a palindrome.

Note: In the above approach, if the length of the list is even, we can divide the linked list into two equal halves and compare them for equality. But when the length of the linked list is odd, we can't divide the list into two equal halves. So, in the odd case, we don't check the mid element.

Time Complexity

O(n)

O(n/2) for finding the middle element.

O(n/2) for reversing the second half of the list.

O(n/2) for comparing both halves.

Summing up the above time complexities and removing constants, we get time complexity equal to O(n).

Auxiliary Space Used

O(1): We used only a constant amount of extra space.

Space Complexity

O(n)

Space used for input: O(n)

Auxiliary space used: O(1)

Space used for output: O(1)

So, total space complexity: O(n).

Check if the given String Is a Palindrome or Not, Using Recursion.

Code for Palindrome Linked List Solution 2: Efficient Solution Using Reverse List:

/*
   Asymptotic complexity in terms of length of the input linked list `n`:
   * Time: O(n).
   * Auxiliary space: O(1).
   * Total space: O(n).
   */
   static Boolean is_palindrome(LinkedListNode head) {
       if (head == null || head.next == null) {
           return true;
       }
       LinkedListNode mid_node = find_mid_node(head);
       mid_node.next = reverse_list(mid_node.next);
       mid_node = mid_node.next;
       /*
       In case of a linked list with odd length, length of
       the left half will be 1 greater than the length of the right half.
       */
       while (mid_node != null) {
           if (head.value.intValue() != mid_node.value.intValue()) {
               return false;
           }
           head = head.next;
           mid_node = mid_node.next;
       }
       return true;
   }
   public static LinkedListNode find_mid_node(LinkedListNode head) {
       if (head == null) {
           return head;
       }
       LinkedListNode fast = head;
       LinkedListNode slow = head;
       /*
       Move fast by two and slow by one.
       When fast reaches the tail, slow will point to the middle.
       */
       while (fast.next != null && fast.next.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;
   }
   public static LinkedListNode reverse_list(LinkedListNode head) {
       LinkedListNode current_node = head;
       LinkedListNode previous_node = null;
       LinkedListNode next = null;
       while (current_node != null) {
           next = current_node.next;
           current_node.next = previous_node;
           previous_node = current_node;
           current_node = next;
       }
       return previous_node;
   }

We hope that these solutions to the Palindrome Linked List problem will help you level up your Linked Lists coding skills. Companies such as Amazon, Microsoft, Adobe, etc., include Palindrome Linked List interview questions in their tech interviews. 

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE Webinar to understand the best way to prepare. 

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, FAANG+ instructors, and career coaching to help you nail your next tech interview. 

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

To learn more, register for the FREE Webinar.