234-回文链表

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
605
文章
12
评论
2019年5月6日18:44:08 评论

来源:力扣(LeetCode)

链接:234. 回文链表

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

请判断一个链表是否为回文链表。

示例 1:

  1. 输入:1->2
  2. 输出:false

示例 2:

  1. 输入:1->2->2->1
  2. 输出:true

进阶:

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

二、题解

2.1 暴力法

算法:

  1. 遍历链表并复制一份
  2. 同时把复制出来的链表反转
  3. 使用2个指针分别遍历两个链表对比每个节点

算法复杂度

  • 时间复杂度:O(n),需要遍历两次链表。
  • 空间复杂度:O(n),需要拷贝一份链表。

2.2 快慢指针

判断是否回文数核心思想是先找到链表的中间节点,然后从中间节点开始往两边对比、或者从两边往中间节点对比,以此判断是否为回文数。

算法:

使用2个指针,快指针每次走一步,慢指针每次走两步。当快指针到链表末尾的时候,慢指针在链表中间。这个时候反转后半部分链表,再使用两个指针从链表两端朝中间遍历即可判断出是不是回文。

图示:

当快指针走到末尾的时候,慢指针刚好走到一半,中间节点就在p1和p1前一个节点之间:

234-回文链表

以下是节点个数为奇数时,快慢指针从开始到结束时候的状态,中间节点是p1的前一个节点:

234-回文链表

可以看到不管链表个数是奇数还是偶数,中间节点都是在慢指针p1附近。

优化:

上面的快慢指针算法的执行步骤:

  1. 快指针遍历到末尾(遍历了一半的链表)。
  2. 反转慢指针到快指针这一段(遍历了一半的链表)。
  3. 从两端往中间遍历(遍历了一半的链表)。

整个时间复杂度是O(n),虽然是O(n),但是实际上链表遍历了1.5次。因为要对比整个链表,所以算法的时间复杂度不可能低于O(n),O(n)最理想的情况就是只遍历一次,因此可以想办法优化掉多余的0.5次遍历。

算法如下:

  1. 快慢指针分别遍历链表,遍历的过程中,把慢指针经过的节点反转。
  2. 当快指针走到链表末尾的时候,慢指针依旧在链表中间的位置,但是此时,慢指针前面的节点都已经反转了。
  3. 分别从满指针前后朝两端遍历,对比每个节点。

该算法把前面的步骤1和2合并成了一个操作,减少了一次遍历操作(需要遍历一半链表节点),最后只要遍历1次链表即可完成判断链表是否回文。算法要注意区分奇数个节点和偶数个节点。

当链表节点个数是偶数个的时候,快指针在指向NULL时,p1前面的就是链表的前半段,从p1开始就是后半段:

234-回文链表

链表节点个数是奇数个的时候,p2不会走到NULL(p2要走2步,没有更多的节点了),此时p1在最中间的节点。p1之前是链表的前半段,p1之后就是链表的后半段:

234-回文链表

代码:

这里要注意的是pre指针的作用,从上面的图示中可以发现,不管是奇数还是偶数个节点,反转后都是从slow节点前分隔开的。因此pre的作用就是保存slow前面的节点,用于后续回文数比对。

234-回文链表

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
马谦马谦马谦
  • 本文由 发表于 2019年5月6日18:44:08
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/palindrome-linked-list.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: