【日拱一卒】链表——回文判断
2020-07-12 本文已影响0人
Jackie_Zheng
需求
判断一个链表是否是回文链表
回文的形式大家应该都知道,类似
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
}
不忘初心
老王:你不好好种地,你以后长大能干什么
小王:学算法
老王:学算法?!你数组、链表、栈、队列、堆、排序、查找都整不明白,你学什么算法
小王:我只学链表回文判断
老王:。。。