CareerCup

it's doubly linked list. We can traverse the list from both end. If we consider combined string of all nodes then finally it would be a single string.
we can traverse DLL from both end and compare it character by character. if it matches throughout the operation then it would be palindrome else not.

Question: all the nodes together? all the nodes together in order? any 2 nodes together? any N nodes together?

If the question is: Do all the strings together in order form a palindrome?
Assign a to point to the first character of the first node.
Traverse to the end and assign this to the tail pointer.
Assign b to point to the last character of the tail node.
Check that the value of b == the value of a.
Move a 1 character towards the tail.
Move b 1 character towards the head.
When you run out of characters in a string, move to the next node in the direction you are going.
If b == a, and all values are the same, it is a palindrome.

all the strings in the nodes together palindrome or not....?

Go to last node,say y
x=head;
1.check whether x's string is palindrome with y's.
as there are N nodes in each of x,y...so if if those data is in array we can compare elements easily. If those nodes are also ll,then reverse y and then compare and finally reverse y to obtain original structure.
if not palindrome,return 0;
else goto step2
2.x=x->next;
if x==y
return 1;
y=y->prev;
if(x==y)
return 1;
go to step 1;

how about traversing it only once and we keep storing the strings in two variables. in one jst adding the strings and in another adding after reversing. then we finally compare the two strings character-wise.

We can store everything in stack, and then traverse from start to check whether it is palindrome or not. The only problem is O(n) space complexity, otherwise TC is O(n).

If I simply traverse the list from headNode till the end, and append the strings in a StringBuffer and then check whether it is palindrome or not in a simple for loop, won't that work? It will take O(n)+O(n) time.

public class DoublePalin {
    public DoublePalin() {
        super();
    }

    public static void main(String[] args) {
        DoublePalin doublePalin = new DoublePalin();
        DoublePalin.DoubleList<Character> list = doublePalin.new DoubleList<Character>();
        String str = "aparnasharma";
        for (int i = 0; i < str.length(); i++) {
            list.insert(str.charAt(i));
        }
        System.out.println(list.palinCheck(str.length()));
    }

    class DoubleList<T extends Comparable> {
        private DoubleList<T> next;
        private DoubleList<T> prev;
        private T data;
        private DoubleList<T> head;
        private DoubleList<T> tail;

        public DoubleList() {
            super();
        }

        public DoubleList(T data) {
            this.setData(data);
        }

        public void insert(T data) {
            DoubleList<T> item = new DoubleList<T>(data);
            if (this.getHead() == null) {
                this.setHead(item);
                this.setTail(item);
            } else {
                this.getTail().setNext(item);
                item.setPrev(this.getTail());
                this.setTail(item);
            }
        }

        public boolean palinCheck(int check) {
            DoubleList<T> head = this.getHead();
            if(head==null) return false;
            DoubleList<T> tail = head.getNext()!=null?head.getNext().getNext():null;
            while (tail != null) 
            {
                head = head.getNext();
                tail = tail.getNext()!=null?tail.getNext().getNext():tail.getNext();
            }
            if(check%2!=0) {tail =head.getNext(); head = head.getPrev();}
            else {
                tail = head.getNext();
            }
            while(head!=null) {
                if(head.getData().compareTo(tail.getData())!=0) {
                    return false;
                }
                head = head.getPrev();
                tail = tail.getNext();
            }
            return true;
        }

        public void traverse() {
            DoubleList<T> head = this.getHead();
            if (head == null)
                return;
            while (head != null) {
                System.out.println(head.getData());
                head = head.getNext();
            }
        }
        
        public void retraverse() {
            DoubleList<T> tail = this.getTail();
            if(tail==null) return;
            while(tail!=null) {
                System.out.println(tail.getData());
                tail = tail.getPrev();
            }
        }

        public void setNext(DoubleList<T> next) {
            this.next = next;
        }

        public DoubleList<T> getNext() {
            return next;
        }

        public void setPrev(DoubleList<T> prev) {
            this.prev = prev;
        }

        public DoubleList<T> getPrev() {
            return prev;
        }

        public void setData(T data) {
            this.data = data;
        }

        public T getData() {
            return data;
        }

        public void setHead(DoubleList<T> head) {
            this.head = head;
        }

        public DoubleList<T> getHead() {
            return head;
        }

        public void setTail(DoubleList<T> tail) {
            this.tail = tail;
        }

        public DoubleList<T> getTail() {
            return tail;
        }
        
        public String toString() {
            return this.getData()!=null?this.getData().toString():"";
        }
    }
}

palinCheck --> Logic

1). Move Head Pointer to middle of the list
2). Length is even then move tail to mid.getNext
3). Length is odd then move head to mid.getPrev and tail to mid.getNext
4). If there is any mismatch return false

1. Keep one pointer at start, another at end node
2. Compare first element of start with last element of end
3. If mismatch, return false
4. Otherwise, move start to next element, end to previous
5. If next/previous element does not exist, move to next/previous node and continue. Move them one by one and check exist condition
6. Exist condition, when both pointers are at same node same character

0. Find the total node count and go to the middle of the DLL.
1. Reverse the DLL from its middle
2. Take two pointers - first at the first node and the second at the middle node.
3. Reverse the string of the node pointed by the second pointer and compare the strings. If they are equal or one is a substring of the other, go to next step, otherwise return false.
4. If both the strings are equal then advance both the first and second pointers else advance the pointer whose node's strings is smaller and check if either of the strings is equal or prefix of each other.
5. Repeat steps 3 and 4 until the second pointer gets past the end of the DLL and the first pointer gets to the middle node.
6 Return true.