链表（篇4）链表中的最长回文序列长度（O(1)额外空间）

本文主要是介绍链表（篇4）链表中的最长回文序列长度（O(1)额外空间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个链表，找出该链表中存在的最长回文序列的长度。
例子：

输入：List = 2-> 3-> 7-> 3-> 2-> 12-> 24 
输出：5 
最长的回文是2-> 3-> 7-> 3-> 2 
Input：List = > 4-> 4-> 3-> 14 
输出：2 
最长的回文为4-> 4

在求链表的最长回文序列的长度之前，先看看怎么求一个给定的链表是否是回文序列。

判断链表是否是回文序列

解法1（时间复杂度O（n），空间复杂度O（n））
使用一个栈来保存链表的后半部分，然后将前后部分进行对比。如下图：
这里写图片描述
为了将后半部分撞到栈中，可以使用一个slow和一个fast指针遍历链表，fast每次向前走两下，slow每次向前走一下，这样当fast走到末尾时，slow正好走到中间，利用slow遍历完链表同时将节点撞到栈中。

public boolean isPalindrome(ListNode head){if(head==null)return false;ListNode cur=head;ListNode slow=head;ListNode fast=head;Stack<ListNode> stack=new Stack<ListNode>();//slow 每次走一下，fast每次走两下      while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}//将链表后半部分入栈while(slow.next!=null){stack.push(slow.next);slow=slow.next;}       cur=head;//比较链表的前半部分和栈中的值是否一致while(!stack.isEmpty()&&cur.val==stack.pop().val)cur=cur.next;           return stack.isEmpty();}
//节点结构
class ListNode{ListNode next=null;int val;public ListNode(int val) {this.val = val;}
}

解法2（时间复杂度O（n），空间复杂度O（1））
将后半部分的节点的指针进行反转，这样就可以同时从后往前和从前往后进行比较了如下图：
这里写图片描述

    public boolean isPalindrome1(ListNode head){if(head==null)return false;ListNode slow=head;ListNode fast=head;ListNode cur;ListNode tail;  while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}slow=reverse(slow); //反转后半指针tail=slow;cur=head;//前半部分和后半部分进行比较while(cur!=null&&tail!=null){if(cur.val!=tail.val)return false;cur=cur.next;tail=tail.next;}reverse(slow);//反转后半指针将原链表还原。return true;}//反转函数。public ListNode reverse(ListNode head){ListNode cur=head;ListNode next=head.next;ListNode pre;cur.next=null;while(next!=null){pre=next.next;next.next=cur;cur=next;next=pre;           }return cur;}

链表中的最长回文序列

一个简单的解决方案可能是将链表内容复制到数组，然后在数组中找到最长的回文子数组，但不允许使用此解决方案，因为它需要额外的空间。解法：迭代的反转链表的指针，然后从当前节点开始向两边找最大回文子数组。因为当前节点的前面指针已经反转可以直接遍历。

    public static int countCommon(ListNode List1,ListNode List2){int count=0;while((List1!=null&&List2!=null)&&(List1.val==List2.val)){count++;List1=List1.next;List2=List2.next;}return count;}public static int longestpalindrome(ListNode head){int result=0;ListNode pre=null;ListNode next,current=head;while(current!=null){System.out.println(current.val);next=current.next;current.next=pre;//反转当前节点的指针，从当前节点开始，向两边寻找最大回文result=Math.max(2*countCommon(pre,next)+1, result);//因为回文有两种情况一种是偶数的，一种是奇数的。//所有有两种方式寻找。result=Math.max(2*countCommon(current,next), result);pre=current;current=next;}return result;}