Length of longest palindrome list in a linked list using O(1) extra space - GeeksforGeeks
Given a linked list, find length of the longest palindrome list that exist in that linked list.
http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/
A Simpler and Tail Recursive Method
Read full article from Length of longest palindrome list in a linked list using O(1) extra space - GeeksforGeeks
Given a linked list, find length of the longest palindrome list that exist in that linked list.
Input : List = 2->3->7->3->2->12->24 Output : 5 The longest palindrome list is 2->3->7->3->2 Input : List = 12->4->4->3->14 Output : 2 The longest palindrome list is 4->4
A simple solution could be to copy linked list content to array and then find longest palindromic subarray in array, but this solution is not allowed as it requires extra space.
The idea is based on iterative linked list reverse process. We iterate through given linked list and one by one reverse every prefix of linked list from left. After reversing a prefix, we find the longest common list beginning from reversed prefix and list after the reversed prefix.
Time Complexity : O(n2)
Note that the above code modifies the given linked list and may not work if modifications to linked list are not allowed. However we can finally do one more reverse to get original list back.
int
countCommon(Node *a, Node *b)
{
int
count = 0;
// loop to count coomon in the list starting
// from node a and b
for
(; a && b; a = a->next, b = b->next)
// increment the count for same values
if
(a->data == b->data)
++count;
else
break
;
return
count;
}
// Returns length of the longest palindrome
// sublist in given list
int
maxPalindrome(Node *head)
{
int
result = 0;
Node *prev = NULL, *curr = head;
// loop till the end of the linked list
while
(curr)
{
// The sublist from head to current
// reversed.
Node *next = curr->next;
curr->next = prev;
// check for odd length palindrome
// by finding longest common list elements
// beginning from prev and from next (We
// exclude curr)
result = max(result,
2*countCommon(prev, next)+1);
// check for even length palindrome
// by finding longest common list elements
// beginning from curr and from next
result = max(result,
2*countCommon(curr, next));
// update prev and curr for next iteration
prev = curr;
curr = next;
}
return
result;
}
Given pointer to the head node of a linked list, the task is to reverse the linked list.
Implementation of Iterative Method
static
Node head;
static
class
Node {
int
data;
Node next;
Node(
int
d) {
data = d;
next =
null
;
}
}
/* Function to reverse the linked list */
Node reverse(Node node) {
Node prev =
null
;
Node current = node;
Node next =
null
;
while
(current !=
null
) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return
node;
}
Recursive Method:
1) Divide the list in two parts - first node and rest of the linked list. 2) Call reverse for the rest of the linked list. 3) Link rest to first. 4) Fix head pointer
void
recursiveReverse(
struct
node** head_ref)
{
struct
node* first;
struct
node* rest;
/* empty list */
if
(*head_ref == NULL)
return
;
/* suppose first = {1, 2, 3}, rest = {2, 3} */
first = *head_ref;
rest = first->next;
/* List has only one node */
if
(rest == NULL)
return
;
/* reverse the rest list and put the first element at the end */
recursiveReverse(&rest);
first->next->next = first;
/* tricky step -- see the diagram */
first->next = NULL;
/* fix the head pointer */
*head_ref = rest;
}
A Simpler and Tail Recursive Method
Read full article from Length of longest palindrome list in a linked list using O(1) extra space - GeeksforGeeks