【日拱一卒】链表——回文判断【日拱一卒】链表——回文判

需求
判断一个链表是否是回文链表
回文的形式大家应该都知道，类似

abcba 或者 abccba

这种对称的方式都是回文。
难点
如果将链表形式换成数组，是不是就简单很多了。针对一个长度为n的数组，我们可以一一比对节点0和节点n-1，节点1和节点n-2，直到收尾索引相等。

文章图片
但是这里说的是链表，显然遍历完整个链表，找到尾结点，然后再回溯进行比较显得有些不切实际，况且这里并不是双向链表。
所以这里就要换个思路，重点是从回文的对称性着手。
思路
关键字：快慢指针、链表反转
1、初始化两个指针快指针和慢指针，慢指针每次走一步，快指针每次走两步

文章图片
2、依次遍历整个链表，直到快指针遍历完链表

文章图片
此时fast指针已经率先到达链表的尾结点，停止遍历。因为该链表包含奇数个元素，所以slow节点需要再移动一步。指向节点2。

文章图片
3、此时借助慢指针将后半部分链表反转

文章图片
反转后链表头指针为pre
4、依次遍历比较原来链表和反转后的链表pre的值是否相等，直到pre遍历到尾结点。

文章图片
20200712-6-链表回文5.png 有了如上思路，写出对应代码就是顺理成章的事了。
代码实现

func isPalindrome(head *ListNode) bool { if head == nil || head.Next == nil { return true }fast := head slow := head// 快慢指针，快指针每次移动两步，慢指针每次移动一步 for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next }//如果是奇数，则慢指针再移动一步，到达中心点 if fast != nil { slow = slow.Next }// 慢指针反转 var pre *ListNode = nil for slow != nil { pre, slow, slow.Next =slow, slow.Next, pre }cur := head for cur != nil && pre != nil { if cur.Val == pre.Val { cur = cur.Next pre = pre.Next } else { return false } }return true }

不忘初心
老王：你不好好种地，你以后长大能干什么
小王：学算法
老王：学算法？！你数组、链表、栈、队列、堆、排序、查找都整不明白，你学什么算法
小王：我只学链表回文判断
【【日拱一卒】链表——回文判断】老王：。。。