Linked list of strings forms a palindrome

JavaView on GFG

Intuition

Concatenate all strings in linked list, check if result is a palindrome.

Algorithm

1Build concatenated string. Two-pointer palindrome check.

Common Pitfalls

•Concatenate first, then check. O(total length). Or check character by character across nodes.

Linked list of strings forms a palindrome.java

Java

// Approach: Collect all string values, concatenate, check if the resulting string is a palindrome.
// Time: O(n * len) Space: O(total len)
class Node {
    String data;
    Node next;

    Node(String x) {
        data = x;
        next = null;
    }
}

class Solution {
    public boolean compute(Node root) {
        String s = "";

        while (root.next != null) {
            s += root.data;
            root = root.next;
        }

        s += root.data;

        int i = 0, j = s.length() - 1;

        while (i++ <= j--) {
            if (s.charAt(i) != s.charAt(j))
                return false;
        }

        return true;
    }
}

Was this solution helpful?