# Palindrome linked list : 3 Methods

```   1->2->3->3->2->1->NULL is palindrome linked list where as,
1->3->2->4->2->1->NULL is not a palindrome linked list
```

By definition of palindrome, a linked list is palindrome if it reads forward and backwards same.

To check if string is palindrome, standard way is to keep to pointers, one moving from left to right and other from right to left and at each point we check if  character at this place match. If at any place they don’t match, we will say string is not palindrome and return. Once two pointers cross each other, we say string is palindrome. Now can we apply that algorithm on linked list? No, because we cannot move backward that is from right to left in case of singly linked list. So what is the way?

## Methods to find palindrome linked list

Using stack to find if linked list is palindrome
One way is to put list on stack. Now pop each element from the stack and move forward in original linked list. If all nodes on stack and linked list match, linked list is palindrome.

Palindrome check by reversing linked list
Another way is to reverse the entire linked list into a new linked list and scan both linked list simultaneously in forward direction. If they differ at any point of time, return false. However, this takes O(N) extra space.

We can reduce space required to half by reversing only half of list and compare that will other half. Even we can do away with n/2 extra space by reversing half of list in place and find if list is palindrome and then again reverse half part of linked list.

```1. Get to the middle of linked list
2. Reverse the second half of list
3. Compare first half and second half
3.a If both are identical, list is palindrome
3.b If both are not identical, list are not palindrome```

In above algorithm, there is one catch. What if number of nodes in linked list is odd, then middle node should not be considered as part of any sublist. How can we find if there are odd number of nodes? Well, when we are traversing list to find middle node, if fast pointer is not null, then there are odd number of node.

```#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

typedef struct Node {
int data;
struct Node * next;
} Node;

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}
printf("Null");
}

// We are returning next node as it will be required in calling function
Node * reverseList(Node *node){

Node *current = node;
Node *prev = NULL;
Node *next = node;

while(current){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

while(L1 && L2){
if(L1->data != L2->data) return false;
L1 = L1->next;
L2 = L2->next;
}
if(!(L1 && L2))
return true;

return false;
}

Node *prev = NULL;
Node *midNode = NULL;
/* We are finding the middle node.*/
while(fast && fast->next){
fast = fast->next->next;
/* We are saving previous node because that
will be end of fist list
in case of even number of nodes */
prev = current;
current = current->next;
}

/*Check if there are odd number of nodes,
if fast pointer is null, then
there are even number of nodes, else it's odd number */
if(fast){
midNode = current;
current = current->next;
}

//Let's reverse second half of list

prev->next  = NULL;

//Reverse back second half

//If there are odd number of nodes, midNode should not be null
if(midNode){
prev->next = midNode;
midNode->next = current;
}
else
prev->next = current;

return isPalindrome;
}

int main(void) {

printf("\nOriginal list :");
printf("\nIs list palindrome : %s",
return 0;
}
```

## Recursive method to find if list is palindrome linked list

Recursive method is quite interesting, in this we have two pointers, one moving forward and other moving backward. As we have seen in couple of problems here and here, how can we move a pointer backward in linked list using recursion. How and when to move forward pointer? We need to compare first node of list with last of list; 2nd with n-1th and so on till backward and forward pointers cross each other.

Forward pointer will be at head till the time we reach at the end of list. Once we are at last node, we can compare first and last node and recursion starts unwinding. Recursive call which had previous to last node should be comparing 2nd node and so on, hence as recursion starts unwinding, move forward pointer ahead. And since updated value of that pointer is needed in calling function, use and pass reference to it. Advantage of this method is that we don’t need to modify linked list at any time.

```1. Start with two pointers forward and backward
2. Till there are nodes in list
2.a move backward pointer ahead and keep forward constant
3. Once reached at end
3.a compare forward with backward pointer, if not equal, return false
3.b else move forward pointer ahead```
```#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

typedef struct Node {
int data;
struct Node * next;
} Node;

Node * createNode(int val){
Node * temp = (Node *)malloc(sizeof(Node));
if(temp){
temp->data = val;
temp->next = NULL;
}
return temp;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}
printf("Null");
}

int isPalindromeUtil(Node **forward, Node *backward){
//There are no nodes is lists
if(!backward) return true;

/*we are recursing moving backward pointer ahead.
Backward pointer will start moving backward once
we hit above terminal condition of recursion */
int isPalindrome = isPalindromeUtil(forward, backward->next);

if(!isPalindrome) return isPalindrome;
/*At this point forward is n nodes ahead from start
and backward n nodes away from end n varies from 0 to n
Compare forward and backward
*/
if((*forward)->data != backward->data){
return false;
}
/*Move ahead forward pointer, backward will move back
automatically due to recursion */
*forward = (*forward)->next;

return isPalindrome;
}

/* we are starting with forward pointer and backward at head.
Notice that we passing reference to forward and just pointer for
backward pointer */
}

int main(void) {

printf("\nOriginal list :");
printf("\nIs list palindrome : %s",
return 0;
}
```

Notice that we defined a function isPalindromeRecursiveMethod() and then a Util function. This is very good practice because your main method need not worry about how internals of recursive function are implemented, it only passes head pointer and gets the dissuader output. This is typical case of abstraction of information.
Execution of above program:

Time complexity of palindrome linked list check algorithm using approach 2 is O(N) and space complexity is O(1). Method 3, that is recursive method has time complexity of O(n) and implicit space complexity of O(n).

• Sree Ranjini

The logic for “/* Now there are two loops. one for check even length linked list and

other for odd number of nodes in linked list */” is incorrect . If you consider mid as same number before and after

eg. 1-2-23-23-23-2-1 is a palindrome , but above code will print 0

Above code can be changed to have only 1 piece of code to solve both odd/even sequence and also correcting back to original list

// reverse count nodes
Node * next = reverse_count_1(head, count);
Node* secondhalf = next; //—-> store this for rejoining

/* Now there are two loops. one for check even length linked list and
other for odd number of nodes in linked list */
Node* curr = current;

if (count & 1) curr = current->next; //———> if odd, ignore mid
bool isPalindrome = true;
while (next){
cout << "Comparing " <data << " and " <data <data == next->data){
curr = curr->next;
next = next->next;
}
else
{
isPalindrome = false; break;
}
}
next = reverse_count_1(current, count); //———–>correct back to original sequnce
current->next = secondhalf;

return isPalindrome;