## Tuesday, 27 June 2017

### Check if a singly linked list is palindrome or not

Given a singly linked list of integers, check whether the linked list is palindrome or not using O(1) space complexity.

In this approach, we need to modify the existing linked list.
1) Get the middle of the linked list.
2) Reverse the second half of the linked list.
3) Check if the first half and second half are identical.
4) Construct the original linked list by reversing the second half again and attaching it back to the first half.

package com.geeks;
/**
* Class to check whether integer list is palindrome or not.
* @author rajesh.dixit
*/
public class PalidromeList {
/** Node definition. */
private static class Node {
int data; Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

/**
* @return String palindrome or not.
*/
private static String checkListIsPalindrome(Node head) {
boolean result = false;

System.out.println("List is null");
result = true;
} else {

/** Reverse the second half of linked list. */

/** Reverse the second half of linked list to get original list. */
}
return result == true?"Palindome":"Not Palindrome";
}

/**
* Compare first and second half of list.
* @param length
* @return
*/
private static boolean compareList(Node head, int length) {
int counter = 0;

while(true) {
if(counter++<length) {
end = end.next;
} else {
secHalf = secHalf.next;
end = end.next;
if(end==null) {
break;
}
}
}

boolean result = true;
while(result && secHalf !=null) {
result = (start.data==secHalf.data);
start = start.next;
secHalf = secHalf.next;
}
return result;
}

/** Reverse the second half of the list. */
private static int reverseSecondHalfOfList(Node head) {
Node p2 = p1.next;

int counter = 0;
while(p2!=null) {
counter++;
p2 = p2.next;
if(p2==null) {
break;
}
p1 = p1.next; p2 = p2.next;
}

Node start = p1.next;
Node temp = null;
Node preNext = null;

while (start != null) {
temp = start.next;
start.next = preNext;
preNext = start;
start = temp;
}
p1.next = preNext;
return counter;
}

/** Util method to print the List. */
private static void printList(Node head) {
System.out.println("List is null");
}

return;
}

while(next!=null) {
System.out.print(next.data+" ");
next = next.next;
}
}

/** Driver method. */
public static void main(String[] args) {