问题描述：请判断一个链表是否为回文链表，链表为单向无环链表。
反转后半部分链表：首先使用快慢指针找到中间的那个链表元素，这里分为两种情况，链表个数为奇数的情况，快指针的next为null，且慢指针指向最中间的那个节点。链表个数为偶数的时候，快指针指向null，且慢指针指向分界链表的第一个节点。
public Boolean isPalia(ListNode root)
{
ListNode slow=root;
ListNode fast=root;
while(fast!=null&&fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
}
if(fast!=null)
{
slow=slow.next;
}
//反转slow指向的剩余链表
Stack<ListNode>stack=new Stack<>();
while(slow!=null)
{
stack.push(slow);
slow=slow.next;
}
ListNode theRestNodeHead=statck.pop();
ListNode cur=theRestNodeHead;
while(!stack.isEmpty())
{
ListNode popNode=stack.pop();
cur.next.popNode;
cur=popNode;
}
cur.next=null;
ListNode beforeHalf=root;
ListNode afterHalf=theRestNodeHead;
while(afterHalf!=null)
{
if(afterHalf.val!=beforeHalf){return false;}
beforeHalf=beforeHalf.next;
afterHalf=afterHalf.next;
}
return true;
}
使用栈解决：将链表全部放入栈中，再退出来，这样就可以模仿从后往前遍历的过程了。
pubic Boolean isPalia(ListNode?root)
{
Stack<ListNode>stack=new Stack<>();
ListNode listCur=root;
while(listCur!=null)
{
stack.push(listCur);
listCur=listCur.next;
}
ListNode cur=root;
for(int i=0;i<stack.size();i++)
{
ListNode tempNode=stack.pop();
if(tempNode.val!=cur.val){return false;}
cur=cur.next;
}
return true;
}
递归的方式求解：
ListNode listHeadCur;
public Boolean isPalia(ListNode root)
{
listHeadCur=root;
return check(root);
}
public Boolean check(ListNode root)
{
if(root==null){return true;}
Boolean res= check(root.next);
res=res&&(root.val==listHeadCur.val);
return res;
}