一.题目介绍
1.题目来源
链接：LeetCode
2.题目
给你一个单链表的头节点head ，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105]内
0 <= Node.val <= 9
二.具体实现
1.实现思路
判断是否是回文链表，第一步是需要找到中间节点，并且翻转前边节点，然后依次判断值是否相同，其思路跟做回文子串的基本相同，或者说这个回文系列的题目的思路按这种方法都能解决，下面看看具体实现。
2.实现代码
1)自己的实现方式
public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } //找到中节点 ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } //此时slow就是前半部分,翻转后半部分 ListNode pre = null; ListNode cur = slow.next; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } //此时的pre就是后半部分的头结点 然后判断是否值相同 while (pre != null) { if (pre.val != head.val) { return false; } pre = pre.next; head = head.next; } return true; } 复制代码
2)题友的实现方式
官方的题解:
1.复制链表值到数组列表中
2.使用双指针法判断是否为回文
3.运行结果
三.题后思考
双指针法确实在很多算法题里都遇到了，其用法很普遍，掌握起来也不难，还有就是回文系列的题目都有共通点，做多了就明白里面的'套路'了。
