Palindrome Linked List in Java with O(n) Time Complexity and O(1) Space Complexity

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

Understanding the Problem

The core challenge of this problem is to determine if the values in a singly linked list form a palindrome. A palindrome is a sequence that reads the same backward as forward. This problem is significant in various applications such as text processing, data validation, and more.

Potential pitfalls include handling edge cases like an empty list or a list with a single node, and ensuring the solution is efficient in both time and space.

Approach

To solve this problem, we can consider the following approaches:

Naive Solution

A naive solution would involve copying the linked list values into an array or list, and then checking if the array is a palindrome. This approach, however, uses O(n) space, which is not optimal.

Optimized Solution

To achieve O(n) time complexity and O(1) space complexity, we can use the following approach:

1. Find the middle of the linked list using the slow and fast pointer technique.
2. Reverse the second half of the linked list.
3. Compare the first half and the reversed second half of the list.
4. Restore the list to its original state (optional).

Algorithm

Let's break down the algorithm step-by-step:

1. Use two pointers, slow and fast, to find the middle of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
2. Reverse the second half of the list starting from the node where the slow pointer is currently pointing.
3. Compare the nodes of the first half and the reversed second half. If all corresponding nodes are equal, the list is a palindrome.
4. Optionally, reverse the second half again to restore the original list structure.

Code Implementation

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Step 1: Find the middle of the linked list
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the linked list
        ListNode prev = null, curr = slow, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Step 3: Compare the first half and the reversed second half
        ListNode firstHalf = head, secondHalf = prev;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) return false;
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        // Optional Step 4: Restore the list (not required for the problem)
        // Reverse the second half again to restore the original list structure

        return true;
    }
}

Complexity Analysis

The time complexity of this approach is O(n) because we traverse the list a constant number of times. The space complexity is O(1) because we only use a few extra pointers, regardless of the list size.

Edge Cases

Consider the following edge cases:

• Empty list: The function should return true.
• Single node list: The function should return true.
• List with all identical elements: The function should return true.

Testing

To test the solution comprehensively, consider the following test cases:

• head = [1,2,2,1] (Expected output: true)
• head = [1,2] (Expected output: false)
• head = [1,2,3,2,1] (Expected output: true)
• head = [1,2,3,4,5] (Expected output: false)

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller, manageable parts.
• Think about different approaches and their trade-offs.
• Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to determine if a singly linked list is a palindrome using an efficient approach with O(n) time complexity and O(1) space complexity. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem: Palindrome Linked List
• GeeksforGeeks: Check if a singly linked list is palindrome
• Coding Ninjas: Palindrome Linked List