Palindrome linked list problem is asked as: given a singly linked list, find if linked list is palindrome or not. For example,

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 */ void push(Node **headRef, int data){ Node * newNode = createNode(data); newNode->next = *headRef; *headRef = newNode; } void printList(Node *head){ while(head){ printf("%d->", head->data); head = head->next; } 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; } int compareTwoLinkedLists(Node *L1, Node *L2){ while(L1 && L2){ if(L1->data != L2->data) return false; L1 = L1->next; L2 = L2->next; } if(!(L1 && L2)) return true; return false; } int isPalindromeList(Node *head){ if(!(head && head->next)) return true; Node *current = head; Node *fast = head; 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 Node *reversedSecondHalfHead = reverseList(current); //Terminate first linked list prev->next = NULL; int isPalindrome = compareTwoLinkedLists(head, reversedSecondHalfHead); //Reverse back second half current = reverseList(reversedSecondHalfHead); //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) { Node *head = NULL; push(&head, 3); push(&head, 4); push(&head, 5); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); printf("\nOriginal list :"); printList(head); printf("\nIs list palindrome : %s", isPalindromeList(head) ? "true" :"false"); 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-1^{th} 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 */ void push(Node **headRef, int data){ Node * newNode = createNode(data); newNode->next = *headRef; *headRef = newNode; } void printList(Node *head){ while(head){ printf("%d->", head->data); head = head->next; } 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; } int isPalindromeListRecursiveMethod(Node *head){ /* we are starting with forward pointer and backward at head. Notice that we passing reference to forward and just pointer for backward pointer */ return isPalindromeUtil(&head, head); } int main(void) { Node *head = NULL; push(&head, 3); push(&head, 4); push(&head, 5); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 2); printf("\nOriginal list :"); printList(head); printf("\nIs list palindrome : %s", isPalindromeListRecursiveMethod(head) ? "true" :"false"); 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).

To see more problems on linked lists, please refer : Linked list problems

please share if there is something missing or wrong. If you are interested to contribute to website, please contact us and earn money.

Pingback: Amazon interview experience 5 | Algorithms and Me()