🦁
Voyz的算法笔记
  • Voyz的算法笔记
  • 归纳总结
    • 排序算法
    • 二分法
    • 滑动窗口
    • 双指针
    • 动态规划
    • DFS/回溯算法
    • BFS
    • 贪心算法
  • 排序算法
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 堆排序
    • 计数排序
    • 桶排序
    • 基数排序
  • 数组
    • 数组中第k大的元素
    • 最长上升子数组
    • 构建乘积数组
    • 和为 s 的连续正数序列
    • 和为 s 的两个数字
    • 连续子数组的最大和
    • 排序数组中的出现次数
    • 奇数位于偶数前
    • 数组中超过一半的数字
    • 旋转数组的最小数字
    • 左旋转字符串
    • 合并有序数组
  • 字符串
    • 电话号码的字母组合
    • 判断回文字符串
    • 生成有效括号
    • 找出回文子串
    • 最长公共前缀
    • 翻转单词顺序
    • 替换空格
    • Z字形变换
  • 矩阵
    • 矩阵置零
    • 螺旋矩阵
    • 搜索二维矩阵
    • 旋转图像
    • 杨辉三角
    • 矩阵查找
    • 矩阵中的路径
    • 顺时针打印矩阵
  • 栈和队列
    • 定义栈数据结构
    • 根据身高重建队列
    • 计算后缀表达式
    • 中缀转后缀
    • 包含 min 函数的栈
    • 从尾到头打印链表
    • 队列的最大值
    • 滑动窗口的最大值
    • 用两个栈实现队列
    • 栈的压入、弹出序列
    • 判断括号有效
  • 哈希表
    • 第一个只出现一次的字符
    • 数组中重复的数字
    • LRU 缓存机制
  • 链表
    • 反转链表
    • 反转链表部分链表
    • 复制带随机指针的链表
    • 复制复杂链表
    • 删除倒数第n个节点
    • 合并两个排序的链表
    • 链表倒数第 k 个节点
    • 两个链表的第一个公共节点
    • 删除链表的节点
    • 环形链表入环位置
    • 链表是否有环
    • 判断回文链表
    • K 个一组翻转链表
  • DFS/回溯算法
    • 不重复字母构成字符串
    • 单词搜索
    • 岛屿数量
    • 分割回文串
    • 全排列
    • 数组组合总和
    • 子集
    • 机器人的运动范围
  • BFS
    • 从上到下打印二叉树
    • 从上到下打印二叉树II
    • 从上到下打印二叉树III
    • 二叉树的最小深度
    • 打开转盘锁
  • 动态规划
    • 打家劫舍I
    • 打家劫舍 II
    • 打家劫舍 III
    • 股票问题汇总
    • 零钱兑换
    • 爬楼梯
    • 最大正方形
    • 把数字翻译成字符串
    • 丑数
    • 斐波那契数列
    • 礼物的最大价值
    • 圆圈中最后剩下的数字
    • 添加符号得到目标和方法数
  • 树
    • 【二叉树】翻转
    • 【二叉树】构造by前序中序
    • 【二叉树】构造by中序后序
    • 【二叉树】合并
    • 【二叉树】镜像
    • 【二叉树】判断对称
    • 【二叉树】前中后序遍历
    • 【二叉树】深度
    • 【二叉树】展开为链表
    • 【二叉树】直径
    • 【二叉树】重复的子树
    • 【二叉树】最近公共祖先
    • 【二叉树】B是A的子结构
    • 【二叉搜索树】第K大元素
    • 【二叉搜索树】第K小元素
    • 【二叉搜索树】构造/遍历
    • 【二叉搜索树】判断
    • 【二叉搜索树】判断后序遍历
    • 【二叉搜索树】转累加树
    • 【二叉搜索树】转排序双向链表
    • 【二叉搜索树】最近公共祖先
    • 【红黑树】构造
    • 【路径和】根到叶子节点
    • 【路径和】为某一值的集合
    • 【路径和】最大值
    • 【平衡二叉树】判断
    • 【对称二叉树】判断
    • 【完美二叉树】填充右侧指针
    • 【依赖关系树】打包顺序数组
    • 【最大二叉树】构建
  • 位运算
    • 比特位计数
    • 出现超过一半的数字
    • 汉明距离
    • Pow(x, n)
    • 不用加减乘除做加法
    • 二进制中 1 的个数
    • 两个只出现一次的数字
  • 贪心算法
    • 加油站
    • 剪绳子
    • 跳跃游戏
    • 无重叠区间
    • 用最少数量的箭引爆气球
  • 双指针
    • 接雨水
    • 盛最多水的容器
    • 长度最小的连续子数组
    • n数之和
  • 分治算法
    • 为运算表达式设计优先级
  • 二分法
    • 缺失的数字
    • 旋转数组的最小元素
    • 排序数组中查找左右区间
由 GitBook 提供支持
在本页
  • 一、快慢指针
  • 判断链表中是否含有环
  • 环的入口位置
  • 寻找链表的中点
  • 寻找链表的倒数第 n 个元素
  • 二、左右指针

这有帮助吗?

  1. 归纳总结

双指针

一、快慢指针

判断链表中是否含有环

  • 用两个指针,一个跑得快,一个跑得慢。如果不含有环,跑得快的那个指针最终会遇到 null,说明链表不含环;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。

boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) return true;
    }
    return false;
}

环的入口位置

  • fast 一定比 slow 多走了 k 步,这多走的 k 步其实就是 fast 指针在环里转圈圈,所以 k 的值就是环长度的「整数倍」。

  • 把快慢指针中的任一个重新指向 head,然后两个指针同速前进,k - m 步后就会相遇,相遇之处就是环的起点了。

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

寻找链表的中点

  • 当快指针到达链表尽头时,慢指针就处于链表的中间位置。

ListNode middleNode(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // slow 就在中间位置
    return slow;
}

寻找链表的倒数第 n 个元素

  • 让快指针先走 n 步,然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时,慢指针所在的位置就是倒数第 n 个链表节点。

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast, slow;
    fast = slow = head;
    // 快指针先前进 n 步
    while (n-- > 0) {
        fast = fast.next;
    }
    if (fast == null) {
        // 如果此时快指针走到头了,
        // 说明倒数第 n 个节点就是第一个节点
        return head.next;
    }
    // 让慢指针和快指针同步向前
    while (fast != null && fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // slow.next 就是倒数第 n 个节点,删除它
    slow.next = slow.next.next;
    return head;
}

二、左右指针

  • 二分查找

  • 两数之和

  • 反转数组

  • 滑动窗口

上一页滑动窗口下一页动态规划

最后更新于3年前

这有帮助吗?