快慢指针（java）

快慢指针（java）

文章目录

• 前言
• 一、快慢指针是什么？
• 二、多种情况
• • 奇数
  • • 一起走
    • 慢指针快一步
    • 快指针快一步（无意义）
    • 快指针快两步
  • 偶数
  • • 一起走
    • 慢指针快一步
    • 快指针快一步
    • 快指针快两步

---

前言

快慢指针是链表的一个重要的方法，在面试中常常用来使空间复杂度变小。但是又有很多中情况需要讨论，所以我们所需要做的是不断的练习，否则一旦在面试中卡住就是几个小时，很不爽

---

一、快慢指针是什么？ 就是用两个指针遍历数组，一个指针一次走两步叫快指针，一个指针一次走一步，叫做慢指针。这样在快指针到尾部的时候，慢指针就到了中点。这样就可以找到 链表的中点。 二、多种情况 奇数

当链表的节点个数为奇数的时候，两个指针会怎么样

一起走

假设是一同走的，那么到最后
快指针会到链表的最后一个节点
慢指针会到中点

慢指针快一步

快指针还是走到链表的最后一个节点
慢指针会走到中点的后面一个

快指针快一步（无意义）

快指针会走出链表。最后一个节点的后面变空
慢指针会走到中点

快指针快两步

快指针会走到最后一个节点
慢指针会中点的前面一个指针

偶数

偶数的情况

一起走

快指针到链表的最后一个节点的后面，为空
慢指针会到两个中点的后面一个

慢指针快一步

快指针到链表的最后一个节点的后面，为空
慢指针到两个中点的后面一个节点

快指针快一步

快指针到最后一个节点
慢指针到两个中点的前面

快指针快两步

当只有两个节点的时候会出错
如果不是，快指针会到链表的最后一个节点的后面，为空
慢指针会到两个中点的前面一个