Palindrome Linked List in Java

A palindrome linked list is a linked list in which the sequence of its elements reads the same forwards and backwards. To determine if a linked list is a palindrome, we need to compare the first half of the list with the reversed second half while maintaining the structure.

Example of Palindrome Linked List

Input: Linked list: 1 -> 2 -> 3 -> 2 -> 1

Output: Is the linked list a palindrome? True

Explanation

The linked list 1 -> 2 -> 3 -> 2 -> 1 is a palindrome because the sequence reads the same forward and backward. By reversing the second half (2 -> 1 becomes 1 -> 2), it matches the first half (1 -> 2 -> 3), confirming the list is a palindrome.

Approach 1: Using Two Pointer Technique

Algorithm

Step 1: Check if the list is empty or contains a single node: If the list is empty (head == null) or has only one element (head.next == null), it's trivially a palindrome. The function returns true immediately.

Step 2: Find the middle of the linked list: Use two pointers: slow and fast. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.

Step 3: Reverse the second half of the list: Once the slow pointer reaches the middle, the second half of the list (from slow onward) is reversed. It is done by iterating through the second half and changing each node's next pointer to point to its previous node. After this step, the second half of the list is reversed and the slow pointer will point to the head of this reversed second half.

Step 4: Compare the two halves of the list: Now, compare the first half of the list (from the head) with the reversed second half (starting from the slow pointer).

Step 4.1: Move the two pointers towards the end of their respective halves: After reversing the second half of the list, you now have two pointers: one starting from the head of the list (first half) and the other from the head of the reversed second half (where the slow pointer is positioned).

Step 5: Use two pointers: one starting from the head of the list and the other from the reversed second half. Traverse both halves, comparing the values at each node. If any mismatch is found, return false (indicating that the list is not a palindrome). If all values match, return true (indicating the list is a palindrome).

Step 6: Conclusion: If no mismatches are found during the comparison, the linked list is a palindrome.

Let's implement the above algorithm in Java program.

File Name: PalindromeLinkedList.java

Output:

 
Is the linked list a palindrome? true   

Complexity Analysis

Time Complexity

The time complexity of this algorithm is O(n) because we traverse the linked list twice: once to find the middle and again to compare the two halves. Reversing the second half also takes O(n). Since no additional space is used, the complexity is O(1).

Space Complexity

This algorithm's space complexity is O(1) because it uses only a constant amount of extra space. It relies on a few pointer variables to traverse and manipulate the linked list, but no additional data structures or arrays are used, making it space-efficient.

Approach 2: Using Stack

Algorithm

Step 1: Handle edge cases: If the linked list is empty (head is null) or contains only one node (head.next is null), we can immediately conclude that it is a palindrome. A single element or an empty list reads the same forwards and backwards, so return true.

Step 2: Initialize two pointers: We use two pointers, slow and fast. Both start at the head of the linked list. The slow pointer will move one node at a time, while the fast pointer will move two nodes at a time. The difference in speed allows us to find the middle of the list. When the fast pointer reaches the end of the list, the slow pointer will be at the middle. It is because the fast pointer moves twice as fast as the slow pointer.

Step 3: Push the first half of the list onto a stack: As the slow pointer moves along the list, we push its current node's value onto a stack. The stack works on a "Last In, First Out" (LIFO) principle, meaning that the values from the first half of the list will be stored in reverse order. Skip the middle element (if the list has an odd length):

Step 3.1: If the list has an odd number of elements, the fast pointer will not be null when the slow pointer reaches the middle. In this case, we move the slow pointer one step forward to skip the middle element. The step ensures that we only compare the second half of the list with the first half, which was stored in the stack.

Step 4: Compare the second half of the list with the stack: Now, the slow pointer is at the start of the second half of the list. We start comparing each node in this second half with the values popped from the stack. For each node in the second half, we pop a value from the stack and check if it matches the current node's value. If at any point the values do not match, we return false because the list is not a palindrome.

Step 5: Return the result: If we reach the end of the second half and all values from the second half match the values popped from the stack, we conclude that the linked list is a palindrome and return true.

Let's implement the above algorithm in Java program.

File Name: PalindromeLinkedList.java

Output:

 
Is the linked list a palindrome? true   

Complexity Analysis

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. We traverse the list twice: once to push the first half onto the stack and once to compare the second half with the stack, both of which take linear time.

Space Complexity

The space complexity of this algorithm is O(n), where n is the number of nodes in the linked list. It is due to the stack used to store the first half of the linked list elements for comparison. No extra data structures other than the stack are required.

Approach 3: Using Recursion

Algorithm

Step 1: Setup the Recursion: The idea behind using recursion is to move through the list from the head to the end and compare nodes from the beginning and the end as the recursion unwinds. The recursive function will traverse the list and backtrack to check for symmetry without explicitly reversing the list.

Step 2: Initialization: frontPointer: A pointer (frontPointer) is initialized to the head of the list. It will keep track of the current node from the front during backtracking in the recursion. We initialize the recursion with a call to recursivelyCheck(head) where head is the starting node of the linked list.

Step 3: Base Case (Recursion End Condition): In any recursive function, you need a base case to stop further recursive calls. For the palindrome check, the base case is when we reach the end of the linked list. Condition: When the current node is null, it means we have reached the end of the list. At this point, we return true because we haven't encountered any mismatches yet.

Step 4: Recursive Step (Traverse to End): As we recursively call recursivelyCheck(current.next), the function moves forward node by node in the linked list until it reaches the end. The recursion continues without checking for palindrome properties just yet; it's only concerned with reaching the base case.

Step 5: Backtracking and Comparison: After the base case is reached (i.e., the recursion starts to unwind), we begin comparing nodes. The key idea is to compare the current node's value with the value at the front of the list, which is tracked by the frontPointer.

Step 6: Comparison: At each level of backtracking, we compare the value of the current node with the value of the node pointed to by frontPointer. If the values do not match, we immediately return false because the list is not a palindrome.

Step 7: Final Check: If the recursive function completes all its comparisons and the nodes continue to match, the function will return true, indicating that the linked list is a palindrome. If at any point a mismatch is found, the recursion immediately returns false, and the linked list is deemed not a palindrome.

Step 8: Function Return Value: The final result, whether the linked list is a palindrome, is returned to the main function where the check started. The result is based on whether all pairs of nodes (from front and back) matched.

Let's implement the above algorithm in Java program.

File Name: PalindromeLinkedList.java

Output:

 
Is the linked list a palindrome? true   

Complexity Analysis

Time Complexity

The time complexity of the recursive palindrome check is O(n), where n is the number of nodes in the linked list. Each node is visited once during recursion, and the comparison between the current node and the front pointer happens at each step as the recursion unwinds.

Space Complexity

The space complexity of the recursive palindrome check is O(n) due to the call stack used for recursion. Each recursive call adds a new frame to the stack, and in the worst case, the recursion depth is proportional to the number of nodes in the linked list.