题目转载自Leetcode
请判断一个链表是否为回文链表。
示例 1:
示例 2:
题解
方法一：反转后半部分链表
题解参考自数据结构和算法
反转后半部分链表，将反转后的链表和前半部分链表比较
1.找到链表中点：
快慢指针：fast走两步，slow走一步–>slow为中点
如果链表有奇数个节点，那么找的是正中间的节点
如果链表有偶数个节点，那么找的是正中间右边的节点
2.判断链表是奇数长度还是偶数长度
如果fast不为空(1+2+2+…+2不为空)–>说明链表的长度是奇数个–>找的是slow.next
否则，找的是slow
3.反转以中点（slow或者slow.next）开始的链表(pre,cur,tmp)
反转循环终止的条件是cur!=null，返回值是pre
1）记录当前节点的下一个节点
cur.next=tmp
2)cur的下一个节点指向pre
cur.next=pre
3）pre和cur都向前移动
pre=cur
cur=tmp
4.使得fast重新指向head，开始遍历比较fast.val和slow.val
class Solution {public boolean isPalindrome(ListNode head) {//找到链表中点ListNode fast=head,slow=head;//这块是为了避免执行fast.next.next报错while(fast!=null && fast.next != null){fast=fast.next.next;slow=slow.next;}if(fast!=null) slow=slow.next;slow=reverse(slow);fast=head;while(slow!=null){if(slow.val!=fast.val) return false;slow=slow.next;fast=fast.next;}return true;}private ListNode reverse(ListNode head){ListNode pre=null;ListNode cur=head;ListNode tmp;//这块的终止条件是cur不为nullwhile(cur!=null){tmp=cur.next;cur.next=pre;pre=cur;cur=tmp;}//循环结束时cur=null，所以此处返回prereturn pre;}
}
方法二：将值复制到数组中后用双指针法
算法
一共为两个步骤：
复制链表值到数组列表中。
使用双指针法判断是否为回文。
class Solution {public boolean isPalindrome(ListNode head) {List<Integer> vals = new ArrayList<Integer>();// 将链表的值复制到数组中ListNode currentNode = head;while (currentNode != null) {vals.add(currentNode.val);currentNode = currentNode.next;}// 使用双指针判断是否回文int front = 0;int back = vals.size() - 1;while (front < back) {if (!vals.get(front).equals(vals.get(back))) {return false;}front++;back--;}return true;}
}
方法三、使用栈解决
我们知道栈是先进后出的一种数据结构，这里还可以使用栈先把链表的节点全部存放到栈中，然后再一个个出栈，这样就相当于链表从后往前访问了，我们只需要拿链表的后半部分和前半部分比较即可，没必要全部比较，所以这里可以优化一下。
public boolean isPalindrome(ListNode head) {if (head == null)return true;ListNode temp = head;Stack<Integer> stack = new Stack();//链表的长度int len = 0;//把链表节点的值存放到栈中while (temp != null) {stack.push(temp.val);temp = temp.next;len++;}//len长度除以2len >>= 1;//然后再出栈while (len-- >= 0) {if (head.val != stack.pop())return false;head = head.next;}return true;
}